Submission #1178713

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<random>
#include<array>
#include<sstream>
#include<utility>
#include<set>

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;
  }
};

template<class E>
void debug(const array<signed char,N> &C,const array<signed char,N> &A,const E &as){
  stringstream ss;
  // for(auto e:C){
  //   ss<<int(e)<<' ';
  // }
  // ss<<endl;
  // for(auto e:A){
  //   ss<<int(e)<<' ';
  // }
  // ss<<endl;
  int a[N+N+2]{};
  for(const auto &e:as){
    a[e.action]++;
  }
  ss<<a[0]<<'|';
  for(int i=0;i<N-1;i++){
    ss<<a[i+1]<<' ';
  }
  ss<<a[N]<<'|';
  for(int i=0;i<N-1;i++){
    ss<<a[i+1+N]<<' ';
  }
  ss<<a[N+N]<<'|';
  ss<<a[N+N+1]<<endl;
  cerr<<ss.str();
}

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=8,QH=16,QW=64;
    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);
      {
	set<pair<int,int> > dupe;
	for(int i=0;i<N;i++){
	  if(dupe.emplace(C[i],A[i]).second){
	    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);
	    }
	    {
	      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 nt=cs.T-1;
	    int nd=cs.D;
	    int ncx=cs.cx;
	    if(nt==0){
	      nt=rnfc[ncx%NRN]%10+1;
	      nd=rnfc[ncx%NRN]/10+1;
	      ncx+=1;
	    }
	    {
	      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.T=nt;
		ns.D=nd;
		ns.cx=ncx;
		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-=cs.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

Judge Result