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

Submission #1180187

Source codeソースコード

#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/30+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=18;
    constexpr int QH=16;
    constexpr int QW=16;
    constexpr int NIA=N+N+2;
    int eaction[NIA]{};
    for(int nm=0;nm<NM;nm++){
      vector<S> ques[QH];
      constexpr int NRN=QH+8;
      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+1,rnfc[0]%10+1,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]/10+1;
	    ns.T=rnfc[cs.cx]%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]%10+1;
	      nd=rnfc[ncx]/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++];
		  ca[i]=0;
	        }
	      }
	      ns.score+=ns.D*ns.D;
	      ns.D=rnfc[cs.cx]/10+1;
	      ns.T=rnfc[cs.cx]%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得点 7519840
Source lengthソースコード長 5126 Byte
File nameファイル名
Exec time実行時間 1593 ms
Memory usageメモリ使用量 848 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 141917 / 417500 subtask_01_01.txt
test_02 152520 / 417500 subtask_01_02.txt
test_03 153486 / 417500 subtask_01_03.txt
test_04 148506 / 417500 subtask_01_04.txt
test_05 154762 / 417500 subtask_01_05.txt
test_06 160043 / 417500 subtask_01_06.txt
test_07 150495 / 417500 subtask_01_07.txt
test_08 145045 / 417500 subtask_01_08.txt
test_09 154572 / 417500 subtask_01_09.txt
test_10 156265 / 417500 subtask_01_10.txt
test_11 155923 / 417500 subtask_01_11.txt
test_12 146474 / 417500 subtask_01_12.txt
test_13 155007 / 417500 subtask_01_13.txt
test_14 151509 / 417500 subtask_01_14.txt
test_15 148884 / 417500 subtask_01_15.txt
test_16 153794 / 417500 subtask_01_16.txt
test_17 140675 / 417500 subtask_01_17.txt
test_18 146988 / 417500 subtask_01_18.txt
test_19 150205 / 417500 subtask_01_19.txt
test_20 148705 / 417500 subtask_01_20.txt
test_21 156698 / 417500 subtask_01_21.txt
test_22 146737 / 417500 subtask_01_22.txt
test_23 140968 / 417500 subtask_01_23.txt
test_24 153787 / 417500 subtask_01_24.txt
test_25 155863 / 417500 subtask_01_25.txt
test_26 144973 / 417500 subtask_01_26.txt
test_27 157454 / 417500 subtask_01_27.txt
test_28 149336 / 417500 subtask_01_28.txt
test_29 148912 / 417500 subtask_01_29.txt
test_30 150777 / 417500 subtask_01_30.txt
test_31 153536 / 417500 subtask_01_31.txt
test_32 147217 / 417500 subtask_01_32.txt
test_33 142808 / 417500 subtask_01_33.txt
test_34 148338 / 417500 subtask_01_34.txt
test_35 148856 / 417500 subtask_01_35.txt
test_36 156203 / 417500 subtask_01_36.txt
test_37 157225 / 417500 subtask_01_37.txt
test_38 141483 / 417500 subtask_01_38.txt
test_39 138825 / 417500 subtask_01_39.txt
test_40 149665 / 417500 subtask_01_40.txt
test_41 147787 / 417500 subtask_01_41.txt
test_42 152683 / 417500 subtask_01_42.txt
test_43 155413 / 417500 subtask_01_43.txt
test_44 144779 / 417500 subtask_01_44.txt
test_45 148910 / 417500 subtask_01_45.txt
test_46 157349 / 417500 subtask_01_46.txt
test_47 153219 / 417500 subtask_01_47.txt
test_48 153830 / 417500 subtask_01_48.txt
test_49 142808 / 417500 subtask_01_49.txt
test_50 157626 / 417500 subtask_01_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 1574 ms 848 KB
subtask_01_02.txt AC 1577 ms 720 KB
subtask_01_03.txt AC 1587 ms 720 KB
subtask_01_04.txt AC 1578 ms 720 KB
subtask_01_05.txt AC 1579 ms 716 KB
subtask_01_06.txt AC 1580 ms 724 KB
subtask_01_07.txt AC 1575 ms 720 KB
subtask_01_08.txt AC 1575 ms 704 KB
subtask_01_09.txt AC 1574 ms 720 KB
subtask_01_10.txt AC 1580 ms 720 KB
subtask_01_11.txt AC 1572 ms 720 KB
subtask_01_12.txt AC 1580 ms 596 KB
subtask_01_13.txt AC 1579 ms 720 KB
subtask_01_14.txt AC 1579 ms 720 KB
subtask_01_15.txt AC 1578 ms 720 KB
subtask_01_16.txt AC 1578 ms 720 KB
subtask_01_17.txt AC 1576 ms 720 KB
subtask_01_18.txt AC 1582 ms 644 KB
subtask_01_19.txt AC 1571 ms 724 KB
subtask_01_20.txt AC 1580 ms 596 KB
subtask_01_21.txt AC 1578 ms 720 KB
subtask_01_22.txt AC 1579 ms 716 KB
subtask_01_23.txt AC 1576 ms 716 KB
subtask_01_24.txt AC 1590 ms 720 KB
subtask_01_25.txt AC 1575 ms 724 KB
subtask_01_26.txt AC 1579 ms 592 KB
subtask_01_27.txt AC 1588 ms 724 KB
subtask_01_28.txt AC 1585 ms 648 KB
subtask_01_29.txt AC 1570 ms 716 KB
subtask_01_30.txt AC 1588 ms 720 KB
subtask_01_31.txt AC 1570 ms 724 KB
subtask_01_32.txt AC 1580 ms 720 KB
subtask_01_33.txt AC 1570 ms 724 KB
subtask_01_34.txt AC 1574 ms 724 KB
subtask_01_35.txt AC 1569 ms 720 KB
subtask_01_36.txt AC 1574 ms 716 KB
subtask_01_37.txt AC 1574 ms 720 KB
subtask_01_38.txt AC 1582 ms 720 KB
subtask_01_39.txt AC 1578 ms 640 KB
subtask_01_40.txt AC 1575 ms 720 KB
subtask_01_41.txt AC 1580 ms 724 KB
subtask_01_42.txt AC 1576 ms 720 KB
subtask_01_43.txt AC 1575 ms 724 KB
subtask_01_44.txt AC 1593 ms 724 KB
subtask_01_45.txt AC 1578 ms 720 KB
subtask_01_46.txt AC 1583 ms 724 KB
subtask_01_47.txt AC 1578 ms 716 KB
subtask_01_48.txt AC 1578 ms 720 KB
subtask_01_49.txt AC 1575 ms 724 KB
subtask_01_50.txt AC 1569 ms 720 KB