Submission #1173574

---

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;
    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=5;
        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)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{
                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

Judge Result