RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1177307

Source codeソースコード

#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

Task問題 A - 石油王Xの憂鬱
User nameユーザ名 106_ustimaw
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 6207454
Source lengthソースコード長 4146 Byte
File nameファイル名
Exec time実行時間 1251 ms
Memory usageメモリ使用量 1000 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 122688 / 417500 subtask_01_01.txt
test_02 119122 / 417500 subtask_01_02.txt
test_03 129227 / 417500 subtask_01_03.txt
test_04 121887 / 417500 subtask_01_04.txt
test_05 120430 / 417500 subtask_01_05.txt
test_06 134580 / 417500 subtask_01_06.txt
test_07 131918 / 417500 subtask_01_07.txt
test_08 119449 / 417500 subtask_01_08.txt
test_09 131839 / 417500 subtask_01_09.txt
test_10 122159 / 417500 subtask_01_10.txt
test_11 133155 / 417500 subtask_01_11.txt
test_12 120606 / 417500 subtask_01_12.txt
test_13 125948 / 417500 subtask_01_13.txt
test_14 130769 / 417500 subtask_01_14.txt
test_15 125797 / 417500 subtask_01_15.txt
test_16 129774 / 417500 subtask_01_16.txt
test_17 118271 / 417500 subtask_01_17.txt
test_18 122191 / 417500 subtask_01_18.txt
test_19 130062 / 417500 subtask_01_19.txt
test_20 127263 / 417500 subtask_01_20.txt
test_21 127714 / 417500 subtask_01_21.txt
test_22 125578 / 417500 subtask_01_22.txt
test_23 123202 / 417500 subtask_01_23.txt
test_24 127611 / 417500 subtask_01_24.txt
test_25 124683 / 417500 subtask_01_25.txt
test_26 113848 / 417500 subtask_01_26.txt
test_27 129722 / 417500 subtask_01_27.txt
test_28 128892 / 417500 subtask_01_28.txt
test_29 129736 / 417500 subtask_01_29.txt
test_30 112782 / 417500 subtask_01_30.txt
test_31 122006 / 417500 subtask_01_31.txt
test_32 118094 / 417500 subtask_01_32.txt
test_33 125814 / 417500 subtask_01_33.txt
test_34 116704 / 417500 subtask_01_34.txt
test_35 128887 / 417500 subtask_01_35.txt
test_36 128013 / 417500 subtask_01_36.txt
test_37 120892 / 417500 subtask_01_37.txt
test_38 118008 / 417500 subtask_01_38.txt
test_39 120652 / 417500 subtask_01_39.txt
test_40 120715 / 417500 subtask_01_40.txt
test_41 135125 / 417500 subtask_01_41.txt
test_42 122220 / 417500 subtask_01_42.txt
test_43 120643 / 417500 subtask_01_43.txt
test_44 107461 / 417500 subtask_01_44.txt
test_45 122587 / 417500 subtask_01_45.txt
test_46 133963 / 417500 subtask_01_46.txt
test_47 122544 / 417500 subtask_01_47.txt
test_48 116055 / 417500 subtask_01_48.txt
test_49 121381 / 417500 subtask_01_49.txt
test_50 124787 / 417500 subtask_01_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 1248 ms 964 KB
subtask_01_02.txt AC 1242 ms 976 KB
subtask_01_03.txt AC 1242 ms 972 KB
subtask_01_04.txt AC 1241 ms 968 KB
subtask_01_05.txt AC 1245 ms 968 KB
subtask_01_06.txt AC 1239 ms 964 KB
subtask_01_07.txt AC 1249 ms 960 KB
subtask_01_08.txt AC 1247 ms 972 KB
subtask_01_09.txt AC 1240 ms 964 KB
subtask_01_10.txt AC 1246 ms 964 KB
subtask_01_11.txt AC 1248 ms 984 KB
subtask_01_12.txt AC 1243 ms 964 KB
subtask_01_13.txt AC 1237 ms 972 KB
subtask_01_14.txt AC 1244 ms 964 KB
subtask_01_15.txt AC 1250 ms 976 KB
subtask_01_16.txt AC 1241 ms 964 KB
subtask_01_17.txt AC 1237 ms 960 KB
subtask_01_18.txt AC 1236 ms 1000 KB
subtask_01_19.txt AC 1237 ms 972 KB
subtask_01_20.txt AC 1246 ms 956 KB
subtask_01_21.txt AC 1244 ms 964 KB
subtask_01_22.txt AC 1247 ms 972 KB
subtask_01_23.txt AC 1244 ms 964 KB
subtask_01_24.txt AC 1251 ms 964 KB
subtask_01_25.txt AC 1244 ms 960 KB
subtask_01_26.txt AC 1240 ms 968 KB
subtask_01_27.txt AC 1250 ms 872 KB
subtask_01_28.txt AC 1240 ms 964 KB
subtask_01_29.txt AC 1236 ms 960 KB
subtask_01_30.txt AC 1246 ms 972 KB
subtask_01_31.txt AC 1241 ms 972 KB
subtask_01_32.txt AC 1250 ms 972 KB
subtask_01_33.txt AC 1251 ms 968 KB
subtask_01_34.txt AC 1247 ms 960 KB
subtask_01_35.txt AC 1239 ms 876 KB
subtask_01_36.txt AC 1242 ms 972 KB
subtask_01_37.txt AC 1246 ms 964 KB
subtask_01_38.txt AC 1246 ms 956 KB
subtask_01_39.txt AC 1247 ms 968 KB
subtask_01_40.txt AC 1249 ms 960 KB
subtask_01_41.txt AC 1238 ms 968 KB
subtask_01_42.txt AC 1244 ms 968 KB
subtask_01_43.txt AC 1242 ms 972 KB
subtask_01_44.txt AC 1246 ms 960 KB
subtask_01_45.txt AC 1244 ms 992 KB
subtask_01_46.txt AC 1243 ms 964 KB
subtask_01_47.txt AC 1243 ms 964 KB
subtask_01_48.txt AC 1245 ms 964 KB
subtask_01_49.txt AC 1239 ms 968 KB
subtask_01_50.txt AC 1242 ms 968 KB