Submission #1174142
Source Code Expand
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision
#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif
using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL MOD=1E9+7;
struct Action{
string str;
vector<int> ints;
};
struct FillTime{
int time,mask;
FillTime():time(0),mask(0){}
FillTime(int a, int b):time(a),mask(b){}
};
struct Problem{
int n,d,t,smallest,largest;
vector<int> cap,now,half;
vector<vector<FillTime>> can_sell;
Problem(LL n):n(n),cap(n),now(n),can_sell(81){};
const int turn= 1000;
queue<Action> to_do;
void solve(){
const int border=1;
const int change_lim=1;
for(int i=0; i<turn; ++i){
#if MYDEBUG
usleep(10000);
#endif
input();
if(!to_do.empty()){
act();
continue;
}
bf(); //タンクの容量いっぱいに入れる場合だけ
int mask=-1,tt=t;
for(auto && i: can_sell[d]){
if(i.time<tt)tt=i.time,mask=i.mask;
}
if(mask!=-1){ //詰めて売る
vector<int> to_sell={0};
for(int b=0; b<8; ++b){
if(mask&(1<<b)){
if(now[b]!=cap[b])to_do.push({"fill",{b+1}});
to_sell[0]++;
to_sell.push_back(b+1);
}
}
//暇ならfillしておく
for(int b=0; b<8; ++b){
if(!(mask&(1<<b)) && (int)to_do.size()<t-1){
if(now[b]==0)to_do.push({"fill",{b+1}});
}
}
to_do.push({"sell",to_sell});
}else if(mask==-1){
if(t<change_lim){
//暇ならfillしておく
for(int b=0; b<8; ++b){
if((int)to_do.size()<t-1){
if(now[b]==0)to_do.push({"fill",{b+1}});
}
}
to_do.push({"pass",{}});
}
else{
to_do.push(judge());
}
}else{ //dが小さいとき
to_do.push(judge());
}
act();
}
}
double evaluate(vector<int> c, vector<int> a,int changed=-1,int filled=-1){
double ret=0;
vector<int> exp_time(81,10);
if(filled>-1)a[filled]=c[filled];
for(int i=1; i<255; ++i){
int oil=0,t=0;
for(int b=0; b<8; ++b){
if(b!=changed && (i&(1<<b))){
oil+=c[b];
if(a[b]<c[b])++t;
}
}
exp_time[oil]=min(exp_time[oil],t);
}
if(changed==-1){
for(int i=1; i<=50; ++i){
ret+=max(0.0,(10.0-exp_time[i])*i*i/(exp_time[i]+1));
}
return ret/500;
}
for(int draw=1; draw<=10; ++draw){
vector<int> tmp=exp_time;
for(int i=50; i>=draw; --i){
tmp[i]=min(tmp[i],exp_time[i-draw]+1);
}
for(int i=1; i<=50; ++i){
ret+=max(0.0,(10.0-tmp[i])*i*i/(tmp[i]+1));
}
}
return ret/5000;
}
Action judge(){
Action ret={"pass",{}};
int best=evaluate(cap,now);
DBG(best)
vector<int> tmpc=cap,tmpa=now;
for(int i=0; i<8; ++i){
int fill_score=evaluate(tmpc,tmpa,-1,i);
DBG(i,fill_score)
if(best<fill_score){
best=fill_score;
ret={"fill",{i+1}};
}
}
for(int i=0; i<8; ++i){
int change_score=evaluate(tmpc,tmpa,i);
DBG(i,change_score)
if(best<change_score){
best=change_score;
ret={"change",{i+1}};
}
}
cerr<<flush;
return ret;
}
double evaluate_specific(vector<int> c, vector<int> a,int changed=-1,int filled=-1){
double ret=0;
vector<int> exp_time(81,10);
if(filled>-1)a[filled]=c[filled];
for(int i=1; i<255; ++i){
int oil=0,t=0;
for(int b=0; b<8; ++b){
if(b!=changed && (i&(1<<b))){
oil+=c[b];
if(a[b]<c[b])++t;
}
}
exp_time[oil]=min(exp_time[oil],t);
}
if(changed==-1){
ret+=max(0.0,(10.0-exp_time[d])*d*d/(exp_time[d]+1));
return ret/10;
}
for(int draw=1; draw<=10; ++draw){
vector<int> tmp=exp_time;
for(int i=50; i>=draw; --i){
tmp[i]=min(tmp[i],exp_time[i-draw]+1);
}
for(int i=1; i<=50; ++i){
ret+=max(0.0,(10.0-tmp[i])*i*i/(tmp[i]+1));
}
}
return ret/5000;
}
Action judge_specific(){
Action ret={"pass",{}};
int best=evaluate_specific(cap,now);
DBG(best)
vector<int> tmpc=cap,tmpa=now;
for(int i=0; i<8; ++i){
int fill_score=evaluate_specific(tmpc,tmpa,-1,i);
DBG(i,fill_score)
if(best<fill_score){
best=fill_score;
ret={"fill",{i+1}};
}
}
for(int i=0; i<8; ++i){
int change_score=evaluate_specific(tmpc,tmpa,i);
DBG(i,change_score)
if(best<change_score){
best=change_score;
ret={"change",{i+1}};
}
}
cerr<<flush;
return ret;
}
void bf(){
can_sell=vector<vector<FillTime>>(81,vector<FillTime>());
for(int i=1; i<255; ++i){
int oil=0,t=0;
for(int b=0; b<8; ++b){
if(i&(1<<b)){
oil+=cap[b];
if(now[b]<cap[b])++t;
}
}
can_sell[oil].push_back({t,i});
}
}
void input(){
cin >> d >> t;
for(int i=0; i<n; ++i){
cin >> cap[i];
}
for(int i=0; i<n; ++i){
cin >> now[i];
}
}
void act(){
cout << to_do.front().str;
for(auto i : to_do.front().ints)cout << ' ' <<i;
cout << endl;
to_do.pop();
}
};
int main(){
//cin.tie(0);
//ios_base::sync_with_stdio(false);
long long n=8;
Problem p(n);
p.solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
Hoi_koro |
Language |
C++14 (GCC 5.4.1) |
Score |
5951985 |
Code Size |
6959 Byte |
Status |
AC |
Exec Time |
121 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 |
122359 / 417500 |
122181 / 417500 |
111143 / 417500 |
118390 / 417500 |
120515 / 417500 |
125416 / 417500 |
123291 / 417500 |
129270 / 417500 |
118441 / 417500 |
124860 / 417500 |
130104 / 417500 |
121245 / 417500 |
128492 / 417500 |
119826 / 417500 |
118809 / 417500 |
121460 / 417500 |
110956 / 417500 |
107537 / 417500 |
114113 / 417500 |
111719 / 417500 |
118473 / 417500 |
113773 / 417500 |
109844 / 417500 |
116524 / 417500 |
121549 / 417500 |
114364 / 417500 |
124736 / 417500 |
114663 / 417500 |
126758 / 417500 |
117359 / 417500 |
120882 / 417500 |
119692 / 417500 |
118193 / 417500 |
125034 / 417500 |
124676 / 417500 |
120875 / 417500 |
116920 / 417500 |
122771 / 417500 |
126172 / 417500 |
116789 / 417500 |
111430 / 417500 |
118910 / 417500 |
121278 / 417500 |
109790 / 417500 |
115657 / 417500 |
121103 / 417500 |
118578 / 417500 |
118784 / 417500 |
107494 / 417500 |
118787 / 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 |
91 ms |
720 KB |
subtask_01_02.txt |
AC |
102 ms |
712 KB |
subtask_01_03.txt |
AC |
106 ms |
720 KB |
subtask_01_04.txt |
AC |
121 ms |
716 KB |
subtask_01_05.txt |
AC |
110 ms |
720 KB |
subtask_01_06.txt |
AC |
103 ms |
720 KB |
subtask_01_07.txt |
AC |
91 ms |
720 KB |
subtask_01_08.txt |
AC |
105 ms |
720 KB |
subtask_01_09.txt |
AC |
105 ms |
724 KB |
subtask_01_10.txt |
AC |
103 ms |
720 KB |
subtask_01_11.txt |
AC |
113 ms |
724 KB |
subtask_01_12.txt |
AC |
108 ms |
716 KB |
subtask_01_13.txt |
AC |
110 ms |
720 KB |
subtask_01_14.txt |
AC |
104 ms |
724 KB |
subtask_01_15.txt |
AC |
104 ms |
716 KB |
subtask_01_16.txt |
AC |
101 ms |
724 KB |
subtask_01_17.txt |
AC |
103 ms |
716 KB |
subtask_01_18.txt |
AC |
107 ms |
720 KB |
subtask_01_19.txt |
AC |
113 ms |
720 KB |
subtask_01_20.txt |
AC |
101 ms |
720 KB |
subtask_01_21.txt |
AC |
96 ms |
720 KB |
subtask_01_22.txt |
AC |
106 ms |
716 KB |
subtask_01_23.txt |
AC |
105 ms |
596 KB |
subtask_01_24.txt |
AC |
109 ms |
720 KB |
subtask_01_25.txt |
AC |
113 ms |
720 KB |
subtask_01_26.txt |
AC |
107 ms |
720 KB |
subtask_01_27.txt |
AC |
106 ms |
716 KB |
subtask_01_28.txt |
AC |
103 ms |
720 KB |
subtask_01_29.txt |
AC |
107 ms |
720 KB |
subtask_01_30.txt |
AC |
106 ms |
724 KB |
subtask_01_31.txt |
AC |
112 ms |
720 KB |
subtask_01_32.txt |
AC |
96 ms |
720 KB |
subtask_01_33.txt |
AC |
112 ms |
720 KB |
subtask_01_34.txt |
AC |
112 ms |
720 KB |
subtask_01_35.txt |
AC |
112 ms |
596 KB |
subtask_01_36.txt |
AC |
106 ms |
720 KB |
subtask_01_37.txt |
AC |
107 ms |
720 KB |
subtask_01_38.txt |
AC |
112 ms |
720 KB |
subtask_01_39.txt |
AC |
104 ms |
720 KB |
subtask_01_40.txt |
AC |
107 ms |
716 KB |
subtask_01_41.txt |
AC |
105 ms |
720 KB |
subtask_01_42.txt |
AC |
102 ms |
720 KB |
subtask_01_43.txt |
AC |
101 ms |
720 KB |
subtask_01_44.txt |
AC |
97 ms |
720 KB |
subtask_01_45.txt |
AC |
92 ms |
720 KB |
subtask_01_46.txt |
AC |
107 ms |
720 KB |
subtask_01_47.txt |
AC |
110 ms |
712 KB |
subtask_01_48.txt |
AC |
101 ms |
720 KB |
subtask_01_49.txt |
AC |
106 ms |
720 KB |
subtask_01_50.txt |
AC |
100 ms |
720 KB |