Submission #1177346
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
#define pops(x) __builtin_popcount(x)
using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL MOD=1E9+7;
constexpr double eps=1e-7;
struct Action{
string str;
vector<int> ints;
};
int change_cnt,pass_cnt;
vector<int> sold(10),came(10);
struct Problem{
const int turn= 1000;
const int cap_combination=24310;
const vector<int> ttttt={1000,100,10,1};
const int bound=31;
//const vector<int> sell_thre={20,26,30,34,37,39,42,44,46,48};
const vector<int> sell_thre={20,22,24,26,28,30,32,34,36,38};
const int search_width=5;
const int c_f=40;
const double score_per_turn=75.0;
int n,d,t;
vector<vector<int>> index;
vector<vector<vector<int>>> graph;
vector<vector<vector<int>>> sellable_masks;
vector<vector<pair<int,double>>> shortest_time;
vector<vector<int>> best_change;
vector<double> state_value;
unordered_map<LL,int> mp;
vector<int> capacity,amount,tank_num;
queue<Action> Q;
bool give_up;
Problem(LL n):
n(n),
graph(cap_combination,vector<vector<int>>(8)),
sellable_masks (cap_combination,vector<vector<int>>(51,vector<int>())),
shortest_time (cap_combination,vector<pair<int,double>>(51)),
best_change(cap_combination,vector<int>(51,-1)),
state_value(cap_combination),
capacity(n),
amount(n),
tank_num(n),
give_up(false){};
void solve(){
precalc();
for(int i=0; i<turn; ++i){
input();
if(!Q.empty()){
act();
continue;
}
int tank_state=mp[get_tank_state(capacity)];
int filled= get_filled_mask(capacity, amount);
vector<pair<int,int>> tanks_select;
for(auto i : sellable_masks[tank_state][d]){
tanks_select.emplace_back(pops(i-(i&filled)),i);
}
sort(tanks_select.begin(),tanks_select.end());
auto it=lower_bound(tanks_select.begin(),tanks_select.end(),make_pair(min(threshold(),t),0));
if(it>tanks_select.begin() /*&& d>=sell_thre[(it-1)->first]*/ /*d>=bound*/){ //詰めて売れる
vector<int> to_sell={0};
auto nxt=lower_bound(tanks_select.begin(),tanks_select.end(),make_pair((it-1)->first,0));
int mask=nxt->second-(nxt->second&filled);
DBG(mask,filled,nxt->second)
for(int b=0; b<8; ++b){
if(mask&(1<<b))Q.push({"fill",{tank_num[b]}});
if(nxt->second&(1<<b)){
to_sell[0]++;
to_sell.push_back(tank_num[b]);
}
}
//暇ならfillしておく
for(int b=7; b>=0; --b){
if (!(filled&(1<<b))&& !(mask&(1<<b)) && (int)Q.size()<t-1){
Q.push({"fill",{tank_num[b]}});
}
}
Q.push({"sell",to_sell});
}else if(d>=bound){
//move?
pair<int,int>success_rate;
if(!give_up){
success_rate=change_success_rate(tank_state,filled);
DBG(success_rate)
}
if(!give_up && (double)success_rate.first/ttttt[0]*d*d/t>score_per_turn){//changeして勝負
Q.push({"change",{tank_num[success_rate.second]}});
}else{//降りた
give_up=true;
//if(accumulate(capacity.begin(),capacity.end(),0)<c_f){
if(false){
Q.push({"change",{tank_num[0]}});
}else{
Q.push(change_fill_pass(tank_state,filled));
}
}
}else{ //安いので売らない
Q.push(change_fill_pass(tank_state,filled));
}
#if MYDEBUG
usleep(20000);
cerr<<flush;
#endif
act();
}
}
int threshold(){
for(int i=0; i<8; ++i){
if(d<sell_thre[i])return i;
}
return 8;
}
double evaluate(int state, int mask, int pass=0){
double ret=0.0;
for(int nxt_d=bound; nxt_d<=50; ++nxt_d){
int min_step=10,max_step=8-pops(mask);
//int diff=140-max_step;
//int diff=60+max_step;
int diff=100;
for(auto i : sellable_masks[state][nxt_d]){
min_step=min(min_step,pops(i-(i&mask)));
}
if(min_step<10){
for(int nxt_t=min_step+1; nxt_t<=10; ++nxt_t){
//ret+=(nxt_d*nxt_d+1000-(min(max_step+1,nxt_t)*100)/100;
ret+=(nxt_d*nxt_d+diff*10-(min(max_step+1,nxt_t)+1-pass)*diff)/100;
}
}else{
ret+=nxt_d*nxt_d*shortest_time[state][nxt_d].second;
//
}
}
return ret/(50-bound+1);
}
Action change_fill_pass(int state, int filled){
double pass_score=evaluate(state, filled,1),maxi=pass_score;
DBG(pass_score)
Action ret={"pass",{}};
//change smallest
for(int i=0; i<2; ++i){
double change_score=0.0;
if(i&&(index[state][i]==index[state][i-1])) continue;
vector<pair<int,int>> amount(8),tmp(8);
for(int j=0; j<8; ++j){
amount[j].first=index[state][j];
amount[j].second=((filled>>j)&1);
}
amount[i].second=0;
for(int draw=1; draw<=10; ++draw){//generate new state
tmp=amount;
tmp[i].first=draw;
sort(tmp.begin(),tmp.end());
vector<int> nxt(8);
int new_mask=0;
for(int j=0; j<8; ++j){
nxt[j]=tmp[j].first;
new_mask+=(tmp[j].second<<j);
}
int new_state=mp[get_tank_state(nxt)];
change_score+=evaluate(new_state,new_mask,t==1);
}
change_score/=10;
DBG(change_score)
if(change_score>maxi){
maxi=change_score;
ret={"change",{tank_num[i]}};
}
}
//fill largest empty tank
if(filled!=255){
int b;
for(b=7; b>=0; --b){
if(!((filled>>b)&1)) break;
}
double fill_score=evaluate(state,filled|(1<<b),t==1);
DBG(fill_score)
if(fill_score>maxi){
maxi=fill_score;
ret={"fill",{tank_num[b]}};
}
}
return ret;
}
pair<int,int> change_success_rate(int state, int fill_mask,int depth=1){
int maxi=0,ret=0;
for(int i=0; i<search_width; ++i){
if(i&&(index[state][i]==index[state][i-1])) continue;
vector<pair<int,int>> now(8),tmp(8);
for(int j=0; j<8; ++j){
now[j].first=index[state][j];
now[j].second=((fill_mask>>j)&1);
}
int cnt=0;
now[i].second=0;
for(int draw=1; draw<=10; ++draw){
tmp=now;
tmp[i].first=draw;
sort(tmp.begin(),tmp.end());
vector<int> nxt(8);
int new_mask=0;
for(int j=0; j<8; ++j){
nxt[j]=tmp[j].first;
new_mask+=(tmp[j].second<<j);
}
int new_state=mp[get_tank_state(nxt)];
bool f=false;
for(auto v: sellable_masks[new_state][d]){
if(pops(v-(v&new_mask))<t-depth){
cnt+=ttttt[depth];
f=true;
break;
}
}
if(depth<=2&&!f){
cnt+=change_success_rate(new_state,new_mask,depth+1).first;
}
}
if(cnt>ret)maxi=i,ret=cnt;
}
return {ret,maxi};
}
void precalc(){
vector<int> loop(8);
int cnt=0;
for(loop[0]=1; loop[0]<=10; ++loop[0]){
for(loop[1]=loop[0]; loop[1]<=10; ++loop[1]){
for(loop[2]=loop[1]; loop[2]<=10; ++loop[2]){
for(loop[3]=loop[2]; loop[3]<=10; ++loop[3]){
for(loop[4]=loop[3]; loop[4]<=10; ++loop[4]){
for(loop[5]=loop[4]; loop[5]<=10; ++loop[5]){
for(loop[6]=loop[5]; loop[6]<=10; ++loop[6]){
for(loop[7]=loop[6]; loop[7]<=10; ++loop[7]){
LL tmp=0;
for(int i=0; i<8; ++i){
tmp+=loop[i];
tmp<<=4;
}
index.push_back(loop);
mp[tmp]=cnt;
bf(loop,sellable_masks[cnt],shortest_time[cnt]);
cnt++;
}
}
}
}
}
}
}
}
for(int i=0; i<cap_combination; ++i){
vector<int> tmp;
for(int j=0; j<n; ++j){
for(int k=1;k<=10; ++k){
tmp=index[i];
tmp[j]=k;
sort(tmp.begin(),tmp.end());
int nxt=mp[get_tank_state(tmp)];
graph[i][j].push_back(nxt);
}
}
}
for(int dist=0; dist<2; ++dist){ //距離"dist"まで
for(int i=0; i<cap_combination; ++i){
for(int a=bound; a<=50; ++a){
double maxi=shortest_time[i][a].second*60;
for(int j=0; j<n; ++j){
double tmp=0;
for(int v: graph[i][j]){
tmp+=(5.0-shortest_time[v][a].second*2)*shortest_time[v][a].second;
//tmp+=6*shortest_time[v][a].second/(1.0+shortest_time[v][a].second);
//1/(1+1/x)~=(-2x^2+5x)/6 (0<x<1)
}
if(tmp>maxi){
maxi=tmp;
best_change[i][a]=j;
}
}
shortest_time[i][a].second=maxi/60;
}
}
}
}
void bf(vector<int>&c, vector<vector<int>> &t_table, vector<pair<int,double>> &s){
for(int i=bound; i<=50; ++i){
s[i].second=10000.0; //inf
//
}
for(int filling_tank=1; filling_tank<=255; ++filling_tank){
int amount=0;
int bitcnt=0;
for(int b=0; b<8; ++b){
if((filling_tank>>b)&1){
amount+=c[b];
++bitcnt;
}
}
if(bound<=amount && amount<=50){
t_table[amount].push_back(filling_tank);
s[amount].second=min(s[amount].second,(double)bitcnt);
//
}
}
for(int i=bound; i<=50; ++i){
sort(t_table[i].begin(),t_table[i].end());
s[i].second=1.0/s[i].second;
//
}
}
LL get_tank_state(vector<int> &c){
LL ret=0;
for(int i=0; i<8; ++i){
ret+=c[i];
ret<<=4;
}
return ret;
}
int get_filled_mask(vector<int> &c, vector<int> &a){
int ret=0;
for(int i=0; i<8; ++i){
if(c[i]==a[i])ret+=(1<<i);
}
return ret;
}
void input(){
cin >> d >> t;
vector<vector<int>> p(8,vector<int>(3));
for(int i=0; i<n; ++i){
cin >> p[i][0];
}
for(int i=0; i<n; ++i){
cin >> p[i][1];
p[i][2]=i+1;
}
sort(p.begin(),p.end());
for(int i=0; i<n; ++i){
capacity[i]=p[i][0];
amount[i]=p[i][1];
tank_num[i]=p[i][2];
}
}
void act(){
if(t==1 || Q.front().str=="pass" || Q.front().str =="sell"){
give_up=false;
came[(d-1)/5]++;
if(Q.front().str =="sell")sold[(d-1)/5]++;
}
if(Q.front().str =="change")change_cnt++;
if(Q.front().str =="pass")pass_cnt++;
cout << Q.front().str;
for(auto i : Q.front().ints)cout << ' ' <<i;
cout << endl;
Q.pop();
}
};
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
long long n=8;
Problem p(n);
p.solve();
cerr<<"changed:"<<change_cnt<<"\n";
cerr<<"passed:"<<pass_cnt<<"\n";
for(int i=0; i<10; ++i){
cerr<<i<<' '<<came[i]<<' '<<sold[i]<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
Hoi_koro |
Language |
C++14 (GCC 5.4.1) |
Score |
7756219 |
Code Size |
13839 Byte |
Status |
AC |
Exec Time |
1445 ms |
Memory |
93448 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 |
149628 / 417500 |
152868 / 417500 |
154181 / 417500 |
159380 / 417500 |
144011 / 417500 |
156419 / 417500 |
161438 / 417500 |
154121 / 417500 |
165265 / 417500 |
167489 / 417500 |
162196 / 417500 |
154229 / 417500 |
154671 / 417500 |
155402 / 417500 |
150338 / 417500 |
157852 / 417500 |
155893 / 417500 |
157589 / 417500 |
155660 / 417500 |
153333 / 417500 |
154590 / 417500 |
157802 / 417500 |
146123 / 417500 |
149175 / 417500 |
156438 / 417500 |
153703 / 417500 |
162304 / 417500 |
158375 / 417500 |
153439 / 417500 |
149238 / 417500 |
159648 / 417500 |
149844 / 417500 |
154375 / 417500 |
153425 / 417500 |
154298 / 417500 |
154755 / 417500 |
158244 / 417500 |
152709 / 417500 |
149987 / 417500 |
154411 / 417500 |
158187 / 417500 |
151870 / 417500 |
150276 / 417500 |
160220 / 417500 |
155603 / 417500 |
153142 / 417500 |
156204 / 417500 |
155482 / 417500 |
151638 / 417500 |
158751 / 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 |
990 ms |
91400 KB |
subtask_01_02.txt |
AC |
1154 ms |
91400 KB |
subtask_01_03.txt |
AC |
964 ms |
91404 KB |
subtask_01_04.txt |
AC |
1240 ms |
91404 KB |
subtask_01_05.txt |
AC |
1154 ms |
91404 KB |
subtask_01_06.txt |
AC |
1052 ms |
91400 KB |
subtask_01_07.txt |
AC |
1153 ms |
91396 KB |
subtask_01_08.txt |
AC |
1120 ms |
91400 KB |
subtask_01_09.txt |
AC |
1206 ms |
91396 KB |
subtask_01_10.txt |
AC |
1056 ms |
91400 KB |
subtask_01_11.txt |
AC |
1239 ms |
91400 KB |
subtask_01_12.txt |
AC |
1445 ms |
91400 KB |
subtask_01_13.txt |
AC |
1191 ms |
91408 KB |
subtask_01_14.txt |
AC |
1155 ms |
91404 KB |
subtask_01_15.txt |
AC |
1049 ms |
91404 KB |
subtask_01_16.txt |
AC |
1063 ms |
91396 KB |
subtask_01_17.txt |
AC |
1150 ms |
91404 KB |
subtask_01_18.txt |
AC |
1033 ms |
91404 KB |
subtask_01_19.txt |
AC |
1106 ms |
93448 KB |
subtask_01_20.txt |
AC |
1168 ms |
91404 KB |
subtask_01_21.txt |
AC |
1098 ms |
91404 KB |
subtask_01_22.txt |
AC |
1203 ms |
91400 KB |
subtask_01_23.txt |
AC |
1159 ms |
91400 KB |
subtask_01_24.txt |
AC |
1136 ms |
91404 KB |
subtask_01_25.txt |
AC |
1223 ms |
93448 KB |
subtask_01_26.txt |
AC |
1046 ms |
91400 KB |
subtask_01_27.txt |
AC |
1220 ms |
91400 KB |
subtask_01_28.txt |
AC |
1071 ms |
91392 KB |
subtask_01_29.txt |
AC |
1119 ms |
91404 KB |
subtask_01_30.txt |
AC |
1180 ms |
91400 KB |
subtask_01_31.txt |
AC |
1029 ms |
91400 KB |
subtask_01_32.txt |
AC |
1047 ms |
91404 KB |
subtask_01_33.txt |
AC |
994 ms |
91404 KB |
subtask_01_34.txt |
AC |
1151 ms |
91400 KB |
subtask_01_35.txt |
AC |
1146 ms |
91400 KB |
subtask_01_36.txt |
AC |
1106 ms |
91400 KB |
subtask_01_37.txt |
AC |
1216 ms |
91400 KB |
subtask_01_38.txt |
AC |
1080 ms |
91396 KB |
subtask_01_39.txt |
AC |
1123 ms |
91400 KB |
subtask_01_40.txt |
AC |
1111 ms |
91396 KB |
subtask_01_41.txt |
AC |
1169 ms |
91400 KB |
subtask_01_42.txt |
AC |
1210 ms |
91396 KB |
subtask_01_43.txt |
AC |
1089 ms |
91404 KB |
subtask_01_44.txt |
AC |
1097 ms |
93448 KB |
subtask_01_45.txt |
AC |
1057 ms |
91404 KB |
subtask_01_46.txt |
AC |
1095 ms |
91400 KB |
subtask_01_47.txt |
AC |
1160 ms |
91400 KB |
subtask_01_48.txt |
AC |
1222 ms |
91396 KB |
subtask_01_49.txt |
AC |
980 ms |
91400 KB |
subtask_01_50.txt |
AC |
1100 ms |
91404 KB |