Submission #1174347

---

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(){
        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&& d>10){ //詰めて売る
                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{
                double sa,sb;
                Action a=judge(sa); //諦める
                Action b=judge_specific(sb); //粘る
                if(sa>sb)to_do.push(a);
                else to_do.push(b);
                DBG(sa,sb)
            }
            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(double &s){
        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}};
            }
        }
        s=best;
        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){
            if(exp_time[d]<t)ret+=d*d/(exp_time[d]+1);
            return ret;
        }
        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);
            }
            if(tmp[d]<t)ret+=d*d/(tmp[d]+1);
        }
        return ret/10;
    }
    Action judge_specific(double &s){
        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}};
            }
        }
        s=best;
        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

Judge Result