Submission #1177299
Source Code Expand
#include<iostream>
#include<algorithm>
#include<random>
#include<array>
#include<sstream>
using namespace std;
constexpr int N=8;
mt19937 engine;
int count8(int x){
return __builtin_popcount(x);
}
struct S{
array<signed char,N> C,A;
int D,T;
int score;
int action;
unsigned cx,tx;
int escore;
S(const array<signed char,N> &c,const array<signed char,N> &a,int d,int t,int s,int paction,unsigned cidx,unsigned tidx):C(c),A(a),D(d),T(t),score(s),action(paction),cx(cidx),tx(tidx){
eval();
}
void eval(){
int es=score+D+T;
for(auto e:C){
es+=e;
}
for(auto e:A){
es+=e;
}
escore=es;
}
bool operator<(const S &s)const{
return escore<s.escore;
}
};
int main(){
for(int i=0;i<1000;i++){
int D,T;
cin>>D>>T;
array<signed char,N> C,A;
for(int j=0;j<N;j++){
int i;
cin>>i;
C[j]=i;
}
for(int j=0;j<N;j++){
int i;
cin>>i;
A[j]=i;
}
int sb=0;
{
unsigned long long b[N+1];
b[0]=1;
for(int i=0;i<N;i++){
b[i+1]=b[i]|b[i]<<A[i];
}
if(b[N]>>D&1){
for(int i=N-1,x=D;i>=0;i--){
if(!(b[i]>>x&1)){
sb|=1<<i;
x-=A[i];
}
}
}
}
constexpr int NM=5,QH=20,QW=80;
constexpr int NIA=N+N+2;
int eaction[NIA]{};
for(int nm=0;nm<NM;nm++){
vector<S> ques[QH];
constexpr int NRN=256;
int rnft[NRN],rnfc[NRN];
for(int i=0;i<NRN;i++){
rnft[i]=uniform_int_distribution<>(1,10)(engine);
rnfc[i]=uniform_int_distribution<>(0,499)(engine);
}
int nt=T-1;
int nd=D;
int cx=0;
if(nt==0){
cx=1;
nt=rnfc[0]%10+1;
nd=rnfc[0]/10+1;
}
ques[0].emplace_back(C,A,rnfc[0]/10+1,rnfc[0]%10+1,0,0,1,0);
for(int i=0;i<N;i++){
if(A[i]!=C[i]){
auto ca=A;
ca[i]=C[i];
ques[0].emplace_back(C,ca,nd,nt,0,1+i,cx,0);
}
}
for(int i=0;i<N;i++){
auto ca=A,cc=C;
cc[i]=rnft[0];
ca[i]=0;
ques[0].emplace_back(cc,ca,nd,nt,0,1+N+i,cx,1);
}
if(sb){
auto cc=C,ca=A;
int tx=0;
for(int i=0;i<N;i++){
if(sb>>i&1){
cc[i]=rnft[tx++];
ca[i]=0;
}
}
ques[0].emplace_back(cc,ca,rnfc[0]/10,rnfc[0]%10,D*D,1+N+N,1,tx);
}
int ceaction[NIA]{};
for(int i=0;i<QH-1;i++){
sort(ques[i].rbegin(),ques[i].rend());
for(int j=0;j<min<int>(QW,ques[i].size());j++){
const S &cs=ques[i][j];
{
auto ns=cs;
ns.D=rnfc[cs.cx%NRN]/10+1;
ns.T=rnfc[cs.cx%NRN]%10+1;
ns.cx++;
ns.eval();
ques[i+1].push_back(ns);
}
{
int x=-1;
int ccap=0;
for(int k=0;k<N;k++){
if(cs.A[k]!=cs.C[k]&&ccap<cs.C[k]){
x=k;
ccap=cs.C[k];
}
}
if(x>=0){
auto ns=cs;
ns.A[x]=ns.C[x];
ns.eval();
ques[i+1].push_back(ns);
}
}
{
unsigned long long b[N+1];
b[0]=1;
for(int i=0;i<N;i++){
b[i+1]=b[i]|b[i]<<cs.A[i];
}
if(b[N]>>cs.D&1){
int sb=0;
for(int i=N-1,x=cs.D;i>=0;i--){
if(!(b[i]>>x&1)){
sb|=1<<i;
x-=A[i];
}
}
auto ns=cs;
auto &cc=ns.C,&ca=ns.A;
for(int i=0;i<N;i++){
if(sb>>i&1){
cc[i]=rnft[ns.tx++%NRN];
ca[i]=0;
}
}
ns.score+=ns.D*ns.D;
ns.D=rnfc[cs.cx%NRN]/10+1;
ns.T=rnfc[cs.cx%NRN]%10+1;
ns.cx++;
ns.eval();
ques[i+1].push_back(ns);
}
}
}
for(auto &e:ques[i+1]){
ceaction[e.action]=max(ceaction[e.action],e.score);
}
}
for(int i=0;i<NIA;i++){
eaction[i]+=ceaction[i];
}
}
auto ba=max_element(begin(eaction),end(eaction))-begin(eaction);
if(ba==0){
cout<<"pass"<<endl;
}else if(ba<=N){
cout<<"fill "<<ba<<endl;
}else if(ba<=N+N){
cout<<"change "<<ba-N<<endl;
}else{
cout<<"sell "<<count8(sb);
for(int i=0;i<N;i++){
if(sb>>i&1){
cout<<' '<<i+1;
}
cout<<endl;
}
}
}
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
ustimaw |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4141 Byte |
Status |
WA |
Exec Time |
707 ms |
Memory |
996 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
test_31 |
test_32 |
test_33 |
test_34 |
test_35 |
test_36 |
test_37 |
test_38 |
test_39 |
test_40 |
test_41 |
test_42 |
test_43 |
test_44 |
test_45 |
test_46 |
test_47 |
test_48 |
test_49 |
test_50 |
Score / Max Score |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
test_31 |
subtask_01_31.txt |
test_32 |
subtask_01_32.txt |
test_33 |
subtask_01_33.txt |
test_34 |
subtask_01_34.txt |
test_35 |
subtask_01_35.txt |
test_36 |
subtask_01_36.txt |
test_37 |
subtask_01_37.txt |
test_38 |
subtask_01_38.txt |
test_39 |
subtask_01_39.txt |
test_40 |
subtask_01_40.txt |
test_41 |
subtask_01_41.txt |
test_42 |
subtask_01_42.txt |
test_43 |
subtask_01_43.txt |
test_44 |
subtask_01_44.txt |
test_45 |
subtask_01_45.txt |
test_46 |
subtask_01_46.txt |
test_47 |
subtask_01_47.txt |
test_48 |
subtask_01_48.txt |
test_49 |
subtask_01_49.txt |
test_50 |
subtask_01_50.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
WA |
684 ms |
952 KB |
subtask_01_02.txt |
WA |
678 ms |
960 KB |
subtask_01_03.txt |
WA |
691 ms |
960 KB |
subtask_01_04.txt |
WA |
680 ms |
996 KB |
subtask_01_05.txt |
WA |
673 ms |
964 KB |
subtask_01_06.txt |
WA |
703 ms |
976 KB |
subtask_01_07.txt |
WA |
692 ms |
968 KB |
subtask_01_08.txt |
WA |
682 ms |
964 KB |
subtask_01_09.txt |
WA |
686 ms |
996 KB |
subtask_01_10.txt |
WA |
671 ms |
956 KB |
subtask_01_11.txt |
WA |
681 ms |
964 KB |
subtask_01_12.txt |
WA |
683 ms |
996 KB |
subtask_01_13.txt |
WA |
686 ms |
956 KB |
subtask_01_14.txt |
WA |
698 ms |
968 KB |
subtask_01_15.txt |
WA |
680 ms |
976 KB |
subtask_01_16.txt |
WA |
696 ms |
960 KB |
subtask_01_17.txt |
WA |
693 ms |
956 KB |
subtask_01_18.txt |
WA |
699 ms |
960 KB |
subtask_01_19.txt |
WA |
694 ms |
960 KB |
subtask_01_20.txt |
WA |
683 ms |
964 KB |
subtask_01_21.txt |
WA |
692 ms |
956 KB |
subtask_01_22.txt |
WA |
689 ms |
956 KB |
subtask_01_23.txt |
WA |
706 ms |
960 KB |
subtask_01_24.txt |
WA |
683 ms |
988 KB |
subtask_01_25.txt |
WA |
687 ms |
980 KB |
subtask_01_26.txt |
WA |
707 ms |
968 KB |
subtask_01_27.txt |
WA |
689 ms |
964 KB |
subtask_01_28.txt |
WA |
683 ms |
964 KB |
subtask_01_29.txt |
WA |
687 ms |
956 KB |
subtask_01_30.txt |
WA |
682 ms |
964 KB |
subtask_01_31.txt |
WA |
686 ms |
956 KB |
subtask_01_32.txt |
WA |
687 ms |
960 KB |
subtask_01_33.txt |
WA |
697 ms |
960 KB |
subtask_01_34.txt |
WA |
693 ms |
964 KB |
subtask_01_35.txt |
WA |
694 ms |
964 KB |
subtask_01_36.txt |
WA |
682 ms |
996 KB |
subtask_01_37.txt |
WA |
679 ms |
968 KB |
subtask_01_38.txt |
WA |
693 ms |
960 KB |
subtask_01_39.txt |
WA |
690 ms |
964 KB |
subtask_01_40.txt |
WA |
682 ms |
968 KB |
subtask_01_41.txt |
WA |
681 ms |
952 KB |
subtask_01_42.txt |
WA |
683 ms |
964 KB |
subtask_01_43.txt |
WA |
689 ms |
968 KB |
subtask_01_44.txt |
WA |
685 ms |
992 KB |
subtask_01_45.txt |
WA |
680 ms |
960 KB |
subtask_01_46.txt |
WA |
688 ms |
960 KB |
subtask_01_47.txt |
WA |
696 ms |
964 KB |
subtask_01_48.txt |
WA |
697 ms |
984 KB |
subtask_01_49.txt |
WA |
688 ms |
960 KB |
subtask_01_50.txt |
WA |
687 ms |
960 KB |