Submission #1176048
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;
double estimate;
vector<int> sold(10),came(10);
struct Problem{
const int turn= 1000;
const int c_combination=24310;
const vector<int> ttttt={1000,100,10,1};
const int lb=31;
const int search_width=5;
const int cf_criterion=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>>> times;
vector<vector<pair<int,double>>> shortest_time;
vector<vector<int>> change_next;
vector<double> evaluation;
unordered_map<LL,int> mp;
vector<int> cap,now,perm;
queue<Action> Q;
Problem(LL n):
n(n),
graph(c_combination,vector<vector<int>>(8)),
times (c_combination,vector<vector<int>>(51,vector<int>())),
shortest_time (c_combination,vector<pair<int,double>>(51)),
change_next(c_combination,vector<int>(51,-1)),
evaluation(c_combination),
cap(n),
now(n),
perm(n){};
void solve(){
bool give_up=false;
precalc();
for(int i=0; i<turn; ++i){
input();
if(!Q.empty()){
act();
continue;
}
LL tank_state=mp[get_tank_state(cap)];
int filled= get_bit(cap, now);
vector<pair<int,int>> tanks_select;
for(auto i : times[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(t,0));
if(d>=lb && it>tanks_select.begin()){ //詰めて売る
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",{perm[b]}});
if(nxt->second&(1<<b)){
to_sell[0]++;
to_sell.push_back(perm[b]);
}
}
//暇ならfillしておく
for(int b=7; b>=0; --b){
if (!(filled&(1<<b))&& !(mask&(1<<b)) && (int)Q.size()<t-1){
Q.push({"fill",{perm[b]}});
}
}
Q.push({"sell",to_sell});
}else if(d>=lb){
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){
Q.push({"change",{perm[success_rate.second]}});
}else{
give_up=true;
if(/*0*/accumulate(cap.begin(),cap.end(),0)<cf_criterion){
Q.push({"change",{perm[0]}});
}else{
Q.push(change_fill_pass(tank_state,filled));
}
if(t==1)give_up=false;
}
}else{ //安いので売らない
Q.push(change_fill_pass(tank_state,filled));
}
#if MYDEBUG
usleep(20000);
cerr<<flush;
#endif
act();
}
}
double f(double a, int b){return (8)/(8+8*a-b);}
double g(double a, int b){return (8)/(8+8*a-b+a*b);}
double h(double a, int b){return (8)/(8+8*a-b+a*b/2);}
double evaluate(int state, int mask, int pass=0){
double ret=0.0,ret2=0.0;
for(int nxt_d=lb; 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 : times[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/(min(max_step,nxt_t)+1)/10;
//ret+=(nxt_d*nxt_d+1000-(min(max_step,nxt_t)+1)*100)/100;
ret+=(nxt_d*nxt_d+diff*10-(min(max_step,nxt_t)+1-pass)*diff)/100;
}
}else{
ret+=nxt_d*nxt_d*shortest_time[state][nxt_d].second;
//ret2+=nxt_d*nxt_d*shortest_time[state][nxt_d].second;
//
}
}
return ret/(50-lb+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>> now(8),tmp(8);
for(int j=0; j<8; ++j){
now[j].first=index[state][j];
now[j].second=((filled>>j)&1);
}
now[i].second=0;
for(int draw=1; draw<=10; ++draw){//generate new state
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)];
change_score+=evaluate(new_state,new_mask);
}
change_score/=10;
DBG(change_score)
if(change_score>maxi){
maxi=change_score;
ret={"change",{perm[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));
DBG(fill_score)
if(fill_score>maxi){
maxi=fill_score;
ret={"fill",{perm[b]}};
}
}
if(t==1 || ret.str=="pass")estimate+=maxi;
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: times[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};
}
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_bit(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){
cap[i]=p[i][0];
now[i]=p[i][1];
perm[i]=p[i][2];
}
}
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,times[cnt],shortest_time[cnt]);
cnt++;
}
}
}
}
}
}
}
}
for(int i=0; i<c_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<c_combination; ++i){
for(int a=lb; 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;
//1/(1+1/x)~=(-2x^2+5x)/6 (0<x<1)
}
if(tmp>maxi){
maxi=tmp;
change_next[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=lb; i<=50; ++i){
s[i].second=10000.0;
//
}
for(int fillbit=1; fillbit<=255; ++fillbit){
int amount=0;
int bitcnt=0;
for(int b=0; b<8; ++b){
if((fillbit>>b)&1){
amount+=c[b];
++bitcnt;
}
}
if(lb<=amount && amount<=50){
t_table[amount].push_back(fillbit);
s[amount].second=min(s[amount].second,(double)bitcnt);
//
}
}
for(int i=lb; i<=50; ++i){
sort(t_table[i].begin(),t_table[i].end());
s[i].second=1.0/s[i].second;
//
}
}
void act(){
if(t==1 || Q.front().str=="pass" || Q.front().str =="sell"){
came[(d-1)/5]++;
if(Q.front().str =="sell")sold[(d-1)/5]++;
}
if(Q.front().str =="change")change_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<<change_cnt<<"\n";
cerr<<estimate <<"\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 |
7702104 |
Code Size |
13391 Byte |
Status |
AC |
Exec Time |
1251 ms |
Memory |
93504 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 |
149579 / 417500 |
148028 / 417500 |
151019 / 417500 |
158815 / 417500 |
148099 / 417500 |
158428 / 417500 |
162380 / 417500 |
150988 / 417500 |
156895 / 417500 |
159711 / 417500 |
160916 / 417500 |
152683 / 417500 |
155476 / 417500 |
154562 / 417500 |
145063 / 417500 |
157517 / 417500 |
150974 / 417500 |
151321 / 417500 |
147801 / 417500 |
151026 / 417500 |
159565 / 417500 |
160228 / 417500 |
151874 / 417500 |
153416 / 417500 |
159294 / 417500 |
150609 / 417500 |
152892 / 417500 |
158805 / 417500 |
152919 / 417500 |
152035 / 417500 |
159292 / 417500 |
149366 / 417500 |
157141 / 417500 |
154926 / 417500 |
155930 / 417500 |
152977 / 417500 |
157195 / 417500 |
151037 / 417500 |
151722 / 417500 |
154099 / 417500 |
145036 / 417500 |
154000 / 417500 |
154372 / 417500 |
153697 / 417500 |
153608 / 417500 |
155521 / 417500 |
160214 / 417500 |
153343 / 417500 |
147586 / 417500 |
158124 / 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 |
1081 ms |
91400 KB |
subtask_01_02.txt |
AC |
1122 ms |
91404 KB |
subtask_01_03.txt |
AC |
1020 ms |
91400 KB |
subtask_01_04.txt |
AC |
1251 ms |
91400 KB |
subtask_01_05.txt |
AC |
1188 ms |
91396 KB |
subtask_01_06.txt |
AC |
992 ms |
91404 KB |
subtask_01_07.txt |
AC |
982 ms |
91404 KB |
subtask_01_08.txt |
AC |
1152 ms |
92424 KB |
subtask_01_09.txt |
AC |
1117 ms |
91396 KB |
subtask_01_10.txt |
AC |
1101 ms |
91400 KB |
subtask_01_11.txt |
AC |
1201 ms |
91400 KB |
subtask_01_12.txt |
AC |
1208 ms |
91400 KB |
subtask_01_13.txt |
AC |
1131 ms |
91400 KB |
subtask_01_14.txt |
AC |
1127 ms |
93504 KB |
subtask_01_15.txt |
AC |
1161 ms |
91400 KB |
subtask_01_16.txt |
AC |
1203 ms |
91392 KB |
subtask_01_17.txt |
AC |
1031 ms |
91404 KB |
subtask_01_18.txt |
AC |
1208 ms |
91404 KB |
subtask_01_19.txt |
AC |
1156 ms |
91400 KB |
subtask_01_20.txt |
AC |
1114 ms |
93448 KB |
subtask_01_21.txt |
AC |
1229 ms |
91400 KB |
subtask_01_22.txt |
AC |
1166 ms |
91400 KB |
subtask_01_23.txt |
AC |
1092 ms |
91400 KB |
subtask_01_24.txt |
AC |
1207 ms |
91396 KB |
subtask_01_25.txt |
AC |
1168 ms |
91400 KB |
subtask_01_26.txt |
AC |
1006 ms |
91400 KB |
subtask_01_27.txt |
AC |
1169 ms |
91400 KB |
subtask_01_28.txt |
AC |
1073 ms |
91400 KB |
subtask_01_29.txt |
AC |
1081 ms |
91400 KB |
subtask_01_30.txt |
AC |
1039 ms |
91396 KB |
subtask_01_31.txt |
AC |
1089 ms |
91404 KB |
subtask_01_32.txt |
AC |
1057 ms |
91400 KB |
subtask_01_33.txt |
AC |
1063 ms |
93448 KB |
subtask_01_34.txt |
AC |
1153 ms |
91400 KB |
subtask_01_35.txt |
AC |
1080 ms |
91400 KB |
subtask_01_36.txt |
AC |
1102 ms |
91396 KB |
subtask_01_37.txt |
AC |
1150 ms |
91400 KB |
subtask_01_38.txt |
AC |
1011 ms |
91396 KB |
subtask_01_39.txt |
AC |
1173 ms |
93448 KB |
subtask_01_40.txt |
AC |
1232 ms |
91400 KB |
subtask_01_41.txt |
AC |
1174 ms |
91404 KB |
subtask_01_42.txt |
AC |
1215 ms |
91400 KB |
subtask_01_43.txt |
AC |
1136 ms |
91400 KB |
subtask_01_44.txt |
AC |
1035 ms |
91396 KB |
subtask_01_45.txt |
AC |
1163 ms |
91404 KB |
subtask_01_46.txt |
AC |
1020 ms |
91400 KB |
subtask_01_47.txt |
AC |
1135 ms |
91400 KB |
subtask_01_48.txt |
AC |
1226 ms |
91400 KB |
subtask_01_49.txt |
AC |
978 ms |
91396 KB |
subtask_01_50.txt |
AC |
1035 ms |
91396 KB |