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