Submission #1178788


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(){
    unsigned long long b=1;
    for(int i=0;i<N;i++){
      b|=b<<A[i];
    }
    int s=0;
    for(int i=1;i<=50;i++){
      if(b>>i&1){
	s+=i*i;
      }
    }
    escore=s/50+score;
  }
  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=38;
    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

Submission Time
Task A - 石油王Xの憂鬱
User ustimaw
Language C++14 (GCC 5.4.1)
Score 7130469
Code Size 5112 Byte
Status AC
Exec Time 1602 ms
Memory 852 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 141125 / 417500 138395 / 417500 146485 / 417500 132741 / 417500 144792 / 417500 148439 / 417500 155497 / 417500 139318 / 417500 149782 / 417500 143051 / 417500 155612 / 417500 140019 / 417500 162050 / 417500 145165 / 417500 142085 / 417500 148399 / 417500 140781 / 417500 140799 / 417500 141952 / 417500 146145 / 417500 152516 / 417500 141303 / 417500 137669 / 417500 147141 / 417500 140940 / 417500 140160 / 417500 143868 / 417500 140377 / 417500 146376 / 417500 136692 / 417500 148861 / 417500 132653 / 417500 133823 / 417500 139313 / 417500 138875 / 417500 142843 / 417500 142977 / 417500 139196 / 417500 140123 / 417500 142068 / 417500 148236 / 417500 138212 / 417500 141368 / 417500 135881 / 417500 136829 / 417500 141343 / 417500 152215 / 417500 135366 / 417500 133080 / 417500 137533 / 417500
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 AC 1587 ms 848 KB
subtask_01_02.txt AC 1591 ms 720 KB
subtask_01_03.txt AC 1599 ms 720 KB
subtask_01_04.txt AC 1598 ms 720 KB
subtask_01_05.txt AC 1594 ms 724 KB
subtask_01_06.txt AC 1595 ms 716 KB
subtask_01_07.txt AC 1597 ms 720 KB
subtask_01_08.txt AC 1595 ms 848 KB
subtask_01_09.txt AC 1593 ms 736 KB
subtask_01_10.txt AC 1596 ms 844 KB
subtask_01_11.txt AC 1592 ms 840 KB
subtask_01_12.txt AC 1600 ms 848 KB
subtask_01_13.txt AC 1588 ms 740 KB
subtask_01_14.txt AC 1591 ms 848 KB
subtask_01_15.txt AC 1592 ms 720 KB
subtask_01_16.txt AC 1597 ms 720 KB
subtask_01_17.txt AC 1589 ms 848 KB
subtask_01_18.txt AC 1601 ms 844 KB
subtask_01_19.txt AC 1583 ms 848 KB
subtask_01_20.txt AC 1591 ms 720 KB
subtask_01_21.txt AC 1589 ms 848 KB
subtask_01_22.txt AC 1595 ms 732 KB
subtask_01_23.txt AC 1594 ms 740 KB
subtask_01_24.txt AC 1591 ms 720 KB
subtask_01_25.txt AC 1596 ms 740 KB
subtask_01_26.txt AC 1594 ms 848 KB
subtask_01_27.txt AC 1596 ms 848 KB
subtask_01_28.txt AC 1585 ms 724 KB
subtask_01_29.txt AC 1598 ms 848 KB
subtask_01_30.txt AC 1601 ms 848 KB
subtask_01_31.txt AC 1598 ms 744 KB
subtask_01_32.txt AC 1595 ms 848 KB
subtask_01_33.txt AC 1588 ms 720 KB
subtask_01_34.txt AC 1590 ms 848 KB
subtask_01_35.txt AC 1597 ms 724 KB
subtask_01_36.txt AC 1597 ms 732 KB
subtask_01_37.txt AC 1594 ms 720 KB
subtask_01_38.txt AC 1585 ms 852 KB
subtask_01_39.txt AC 1595 ms 852 KB
subtask_01_40.txt AC 1589 ms 720 KB
subtask_01_41.txt AC 1589 ms 844 KB
subtask_01_42.txt AC 1593 ms 720 KB
subtask_01_43.txt AC 1595 ms 848 KB
subtask_01_44.txt AC 1588 ms 720 KB
subtask_01_45.txt AC 1602 ms 720 KB
subtask_01_46.txt AC 1593 ms 716 KB
subtask_01_47.txt AC 1595 ms 848 KB
subtask_01_48.txt AC 1595 ms 720 KB
subtask_01_49.txt AC 1592 ms 724 KB
subtask_01_50.txt AC 1594 ms 848 KB