Submission #1173637
Source Code Expand
#include <bits/stdc++.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=10;
const int change_lim=4;
for(int i=0; i<turn; ++i){
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 && d*d/t>border){ //詰めて売る
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{
vector<int> cap_cnt(11);
for(int i=0; i<8; ++i){
cap_cnt[cap[i]]++;
}
int to_change=-1,cnt=1;
//オイルがないタンクのうち最も重複するものをchange
/*for(int i=0; i<8; ++i){
if(now[i]==0 && cap_cnt[cap[i]]>cnt){
to_change=i;
cnt=cap_cnt[cap[i]];
}
}*/
//オイルがないタンクのうち最も小さいものをchange
if(to_change==-1){
int mini=INF;
for(int i=0; i<8; ++i){
if(now[i]==0 && cap[i]<mini)mini=cap[i],to_change=i;
}
}
//適当にchange
if(to_change==-1){
random_device rnd;
mt19937 mt(rnd());
uniform_int_distribution<LL> dist(0,7);
to_change=dist(mt);
}
to_do.push({"change",{to_change+1}});
}
}else{
//暇なら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",{}});
}
act();
}
}
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 |
5281690 |
Code Size |
4837 Byte |
Status |
AC |
Exec Time |
51 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 |
105060 / 417500 |
100917 / 417500 |
99219 / 417500 |
107882 / 417500 |
108761 / 417500 |
115225 / 417500 |
107937 / 417500 |
109795 / 417500 |
109847 / 417500 |
115061 / 417500 |
114641 / 417500 |
97772 / 417500 |
118666 / 417500 |
109069 / 417500 |
96090 / 417500 |
114032 / 417500 |
96088 / 417500 |
106867 / 417500 |
112414 / 417500 |
105926 / 417500 |
124106 / 417500 |
109510 / 417500 |
90574 / 417500 |
104819 / 417500 |
105978 / 417500 |
97377 / 417500 |
109693 / 417500 |
107188 / 417500 |
107351 / 417500 |
102212 / 417500 |
106016 / 417500 |
104191 / 417500 |
106886 / 417500 |
103232 / 417500 |
98531 / 417500 |
106279 / 417500 |
90857 / 417500 |
101037 / 417500 |
112058 / 417500 |
102304 / 417500 |
101828 / 417500 |
96930 / 417500 |
107382 / 417500 |
93626 / 417500 |
103457 / 417500 |
105457 / 417500 |
113389 / 417500 |
110890 / 417500 |
110231 / 417500 |
97032 / 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 |
49 ms |
720 KB |
subtask_01_02.txt |
AC |
49 ms |
716 KB |
subtask_01_03.txt |
AC |
49 ms |
720 KB |
subtask_01_04.txt |
AC |
50 ms |
716 KB |
subtask_01_05.txt |
AC |
48 ms |
720 KB |
subtask_01_06.txt |
AC |
47 ms |
592 KB |
subtask_01_07.txt |
AC |
48 ms |
720 KB |
subtask_01_08.txt |
AC |
48 ms |
720 KB |
subtask_01_09.txt |
AC |
48 ms |
720 KB |
subtask_01_10.txt |
AC |
48 ms |
720 KB |
subtask_01_11.txt |
AC |
49 ms |
724 KB |
subtask_01_12.txt |
AC |
51 ms |
720 KB |
subtask_01_13.txt |
AC |
48 ms |
592 KB |
subtask_01_14.txt |
AC |
46 ms |
720 KB |
subtask_01_15.txt |
AC |
49 ms |
720 KB |
subtask_01_16.txt |
AC |
47 ms |
720 KB |
subtask_01_17.txt |
AC |
50 ms |
720 KB |
subtask_01_18.txt |
AC |
49 ms |
720 KB |
subtask_01_19.txt |
AC |
48 ms |
656 KB |
subtask_01_20.txt |
AC |
50 ms |
724 KB |
subtask_01_21.txt |
AC |
47 ms |
716 KB |
subtask_01_22.txt |
AC |
47 ms |
724 KB |
subtask_01_23.txt |
AC |
49 ms |
720 KB |
subtask_01_24.txt |
AC |
49 ms |
720 KB |
subtask_01_25.txt |
AC |
51 ms |
720 KB |
subtask_01_26.txt |
AC |
49 ms |
724 KB |
subtask_01_27.txt |
AC |
50 ms |
720 KB |
subtask_01_28.txt |
AC |
49 ms |
716 KB |
subtask_01_29.txt |
AC |
49 ms |
720 KB |
subtask_01_30.txt |
AC |
48 ms |
720 KB |
subtask_01_31.txt |
AC |
48 ms |
724 KB |
subtask_01_32.txt |
AC |
50 ms |
716 KB |
subtask_01_33.txt |
AC |
51 ms |
720 KB |
subtask_01_34.txt |
AC |
50 ms |
720 KB |
subtask_01_35.txt |
AC |
49 ms |
720 KB |
subtask_01_36.txt |
AC |
47 ms |
720 KB |
subtask_01_37.txt |
AC |
48 ms |
720 KB |
subtask_01_38.txt |
AC |
46 ms |
720 KB |
subtask_01_39.txt |
AC |
46 ms |
720 KB |
subtask_01_40.txt |
AC |
51 ms |
720 KB |
subtask_01_41.txt |
AC |
48 ms |
720 KB |
subtask_01_42.txt |
AC |
48 ms |
720 KB |
subtask_01_43.txt |
AC |
49 ms |
720 KB |
subtask_01_44.txt |
AC |
49 ms |
720 KB |
subtask_01_45.txt |
AC |
45 ms |
716 KB |
subtask_01_46.txt |
AC |
45 ms |
720 KB |
subtask_01_47.txt |
AC |
46 ms |
724 KB |
subtask_01_48.txt |
AC |
50 ms |
724 KB |
subtask_01_49.txt |
AC |
50 ms |
720 KB |
subtask_01_50.txt |
AC |
48 ms |
720 KB |