Submission #1174127


Source Code Expand

#include<iostream>
#include<random>
#include<array>
#include<sstream>

using namespace std;

constexpr int N=8;
mt19937 engine;

int count(int x){
  return __builtin_popcount(x);
}

double rtexp(int r){
  return r*80;
}

template<class E>
double exps(const E &A,const E &C,int D,int T,int r,int rb){
  if(r<=0)return 0;
  if(T==0){
    if(rb<=0)return rtexp(r);
    double res=0;
    for(int i=1;i<=10;i++){
      for(int j=1;j<=50;j++){
	res+=exps(A,C,j,i,r,rb-1)/500;
      }
    }
    return res;
  }
  int dp[51];
  for(int i=1;i<=D;i++){
    dp[i]=1e9;
  }
  dp[0]=0;
  for(int i=0;i<N;i++){
    int m=A[i]?A[i]:C[i];
    for(int j=D;j-m>=0;j--){
      dp[j]=min(dp[j],dp[j-m]+(m!=A[i]));
    }
  }
  auto t=dp[D];
  if(t>=1e8||t+1>T){
    return rtexp(r-1);
  }else{
    return D*D+rtexp(r-t-1);
  }
}

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 t=1e9,b;
    for(int i=0;i<1<<N;i++){
      int c=0;
      int rm=0;
      for(int j=0;j<N;j++){
	if(i>>j&1){
	  c+=C[j];
	  if(A[j]!=C[j]){
	    rm++;
	  }
	}
      }
      if(c==D){
	if(rm<t){
	  t=rm;
	  b=i;
	}
      }
    }
    if(t>1e8){
      auto resd=1000-1-i;
      double es=exps(A,C,D,0,resd,1);
      string res="pass";
      for(int j=0;j<N;j++){
	auto ca=A;
	ca[j]=0;
	double cs=0;
	for(int k=1;k<=10;k++){
	  auto cc=C;
	  cc[j]=k;
	  cs+=exps(ca,cc,D,T-1,resd,1)/10;
	}
	if(cs>es){
	  es=cs;
	  stringstream ss;
	  ss<<"change "<<j+1;
	  res=ss.str();
	}
      }
      cout<<res<<endl;
    }else{
      if(t==0){
	cout<<"sell "<<count(b);
	for(int j=0;j<N;j++){
	  if(b>>j&1){
	    cout<<' '<<j+1;
	  }
	}
	cout<<endl;
      }else{
	for(int j=0;;j++){
	  if(b>>j&1&&A[j]!=C[j]){
	    cout<<"fill "<<j+1<<endl;
	    break;
	  }
	}
      }
    }
  }
}

Submission Info

Submission Time
Task A - 石油王Xの憂鬱
User ustimaw
Language C++14 (GCC 5.4.1)
Score 5084684
Code Size 2052 Byte
Status AC
Exec Time 367 ms
Memory 724 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 101338 / 417500 99376 / 417500 102204 / 417500 91849 / 417500 95644 / 417500 107116 / 417500 110356 / 417500 101128 / 417500 101277 / 417500 106553 / 417500 111835 / 417500 104269 / 417500 109200 / 417500 100062 / 417500 105971 / 417500 110348 / 417500 96779 / 417500 100841 / 417500 111468 / 417500 103838 / 417500 107853 / 417500 102448 / 417500 98703 / 417500 98883 / 417500 109926 / 417500 97944 / 417500 100847 / 417500 101378 / 417500 100554 / 417500 101234 / 417500 107847 / 417500 103991 / 417500 96149 / 417500 99897 / 417500 97110 / 417500 97253 / 417500 99007 / 417500 96250 / 417500 99049 / 417500 99243 / 417500 106061 / 417500 95941 / 417500 110736 / 417500 90151 / 417500 101225 / 417500 100908 / 417500 99271 / 417500 104023 / 417500 93230 / 417500 96120 / 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 287 ms 720 KB
subtask_01_02.txt AC 229 ms 720 KB
subtask_01_03.txt AC 226 ms 720 KB
subtask_01_04.txt AC 314 ms 720 KB
subtask_01_05.txt AC 235 ms 724 KB
subtask_01_06.txt AC 214 ms 720 KB
subtask_01_07.txt AC 205 ms 716 KB
subtask_01_08.txt AC 247 ms 716 KB
subtask_01_09.txt AC 176 ms 724 KB
subtask_01_10.txt AC 236 ms 720 KB
subtask_01_11.txt AC 175 ms 720 KB
subtask_01_12.txt AC 263 ms 716 KB
subtask_01_13.txt AC 226 ms 720 KB
subtask_01_14.txt AC 243 ms 720 KB
subtask_01_15.txt AC 173 ms 720 KB
subtask_01_16.txt AC 166 ms 720 KB
subtask_01_17.txt AC 207 ms 724 KB
subtask_01_18.txt AC 367 ms 724 KB
subtask_01_19.txt AC 207 ms 724 KB
subtask_01_20.txt AC 241 ms 720 KB
subtask_01_21.txt AC 296 ms 720 KB
subtask_01_22.txt AC 179 ms 720 KB
subtask_01_23.txt AC 300 ms 720 KB
subtask_01_24.txt AC 217 ms 720 KB
subtask_01_25.txt AC 210 ms 724 KB
subtask_01_26.txt AC 227 ms 724 KB
subtask_01_27.txt AC 200 ms 720 KB
subtask_01_28.txt AC 310 ms 720 KB
subtask_01_29.txt AC 289 ms 720 KB
subtask_01_30.txt AC 245 ms 716 KB
subtask_01_31.txt AC 220 ms 592 KB
subtask_01_32.txt AC 265 ms 724 KB
subtask_01_33.txt AC 285 ms 720 KB
subtask_01_34.txt AC 253 ms 720 KB
subtask_01_35.txt AC 249 ms 724 KB
subtask_01_36.txt AC 327 ms 720 KB
subtask_01_37.txt AC 240 ms 716 KB
subtask_01_38.txt AC 189 ms 720 KB
subtask_01_39.txt AC 306 ms 720 KB
subtask_01_40.txt AC 239 ms 720 KB
subtask_01_41.txt AC 187 ms 716 KB
subtask_01_42.txt AC 281 ms 720 KB
subtask_01_43.txt AC 188 ms 716 KB
subtask_01_44.txt AC 214 ms 724 KB
subtask_01_45.txt AC 265 ms 724 KB
subtask_01_46.txt AC 167 ms 716 KB
subtask_01_47.txt AC 199 ms 720 KB
subtask_01_48.txt AC 292 ms 720 KB
subtask_01_49.txt AC 206 ms 692 KB
subtask_01_50.txt AC 302 ms 720 KB