Submission #1174281


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(){
        const int border=1;
        const int change_lim=1;
        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){ //詰めて売る
                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

Submission Time
Task A - 石油王Xの憂鬱
User Hoi_koro
Language C++14 (GCC 5.4.1)
Score 5997636
Code Size 6622 Byte
Status AC
Exec Time 167 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 119359 / 417500 124470 / 417500 125850 / 417500 119017 / 417500 120918 / 417500 123224 / 417500 125792 / 417500 126573 / 417500 118333 / 417500 136346 / 417500 127253 / 417500 118930 / 417500 126736 / 417500 122417 / 417500 118494 / 417500 122275 / 417500 114612 / 417500 122953 / 417500 125547 / 417500 118288 / 417500 130116 / 417500 111526 / 417500 116413 / 417500 112054 / 417500 121416 / 417500 113956 / 417500 123237 / 417500 110706 / 417500 116279 / 417500 118133 / 417500 119134 / 417500 110231 / 417500 118712 / 417500 113364 / 417500 126674 / 417500 120425 / 417500 123749 / 417500 119590 / 417500 115384 / 417500 117007 / 417500 116533 / 417500 115423 / 417500 117271 / 417500 111755 / 417500 112881 / 417500 122729 / 417500 120874 / 417500 122872 / 417500 117999 / 417500 123806 / 417500
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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 133 ms 716 KB
subtask_01_02.txt AC 147 ms 720 KB
subtask_01_03.txt AC 148 ms 720 KB
subtask_01_04.txt AC 167 ms 720 KB
subtask_01_05.txt AC 156 ms 716 KB
subtask_01_06.txt AC 144 ms 720 KB
subtask_01_07.txt AC 122 ms 720 KB
subtask_01_08.txt AC 156 ms 720 KB
subtask_01_09.txt AC 149 ms 720 KB
subtask_01_10.txt AC 151 ms 720 KB
subtask_01_11.txt AC 137 ms 720 KB
subtask_01_12.txt AC 139 ms 724 KB
subtask_01_13.txt AC 141 ms 724 KB
subtask_01_14.txt AC 148 ms 720 KB
subtask_01_15.txt AC 160 ms 724 KB
subtask_01_16.txt AC 146 ms 712 KB
subtask_01_17.txt AC 155 ms 716 KB
subtask_01_18.txt AC 164 ms 720 KB
subtask_01_19.txt AC 158 ms 720 KB
subtask_01_20.txt AC 130 ms 720 KB
subtask_01_21.txt AC 150 ms 720 KB
subtask_01_22.txt AC 159 ms 724 KB
subtask_01_23.txt AC 143 ms 724 KB
subtask_01_24.txt AC 146 ms 720 KB
subtask_01_25.txt AC 159 ms 720 KB
subtask_01_26.txt AC 156 ms 720 KB
subtask_01_27.txt AC 157 ms 720 KB
subtask_01_28.txt AC 139 ms 724 KB
subtask_01_29.txt AC 144 ms 720 KB
subtask_01_30.txt AC 153 ms 716 KB
subtask_01_31.txt AC 153 ms 720 KB
subtask_01_32.txt AC 152 ms 720 KB
subtask_01_33.txt AC 162 ms 720 KB
subtask_01_34.txt AC 162 ms 720 KB
subtask_01_35.txt AC 155 ms 720 KB
subtask_01_36.txt AC 164 ms 720 KB
subtask_01_37.txt AC 156 ms 720 KB
subtask_01_38.txt AC 152 ms 720 KB
subtask_01_39.txt AC 131 ms 724 KB
subtask_01_40.txt AC 148 ms 724 KB
subtask_01_41.txt AC 165 ms 720 KB
subtask_01_42.txt AC 155 ms 720 KB
subtask_01_43.txt AC 141 ms 720 KB
subtask_01_44.txt AC 141 ms 724 KB
subtask_01_45.txt AC 146 ms 720 KB
subtask_01_46.txt AC 138 ms 720 KB
subtask_01_47.txt AC 153 ms 720 KB
subtask_01_48.txt AC 134 ms 720 KB
subtask_01_49.txt AC 152 ms 716 KB
subtask_01_50.txt AC 135 ms 724 KB