Submission #1175912

---

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;
vector<int> sold(10),came(10);

struct Problem{
    const int turn= 1000;
    const int capacity_comb=24310;
    const vector<int> ttttt={1000,100,10,1};
    const int lb=26;
    const int width=5;
    const int cf_criterion=40;
    const double score_per_turn=70.0;

    int n,d,t;
    vector<vector<int>> index;
    vector<vector<vector<int>>> graph;
    vector<vector<vector<short>>> times;
    unordered_map<LL,int> mp;
    vector<int> cap,now,perm;
    queue<Action> to_do;
    Problem(LL n):
        n(n),
        graph(capacity_comb,vector<vector<int>>(8)),
        times (capacity_comb,vector<vector<short>>(51,vector<short>())),
        cap(n),
        now(n),
        perm(n){};
    void solve(){
        bool searched=false;
        precalc();
        for(int i=0; i<turn; ++i){
            input();
            if(!to_do.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))to_do.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)to_do.size()<t-1){
                        to_do.push({"fill",{perm[b]}});
                    }
                }
                to_do.push({"sell",to_sell});
            }else if(d>=lb){
                pair<int,int>success_rate;
                if(!searched){
                    success_rate=change_success_rate(tank_state,filled);
                    DBG(success_rate)
                }
                if(!searched && (double)success_rate.first/1000*d*d/t>score_per_turn){
                    to_do.push({"change",{perm[success_rate.second]}});
                }else{
                    searched=true;
                    if(accumulate(cap.begin(),cap.end(),0)<cf_criterion){
                        to_do.push({"change",{perm[0]}});
                    }else{
                        //暇ならfillしておく
                        for(int b=7; b>=0; --b){
                            if(!(filled&(1<<b))){
                                to_do.push({"fill",{perm[b]}});
                                break;
                            }
                            if(b==0){
                                if(t==1)to_do.push({"change",{perm[0]}});
                                else to_do.push({"pass",{}});
                                searched=false;
                            }
                        }
                    }
                    if(t==1)searched=false;
                }
            }else{ //安いので売らない
                for(int b=7; b>=0; --b){
                    if(!(filled&(1<<b))){
                        to_do.push({"fill",{perm[b]}});
                        break;
                    }
                    if(b==0){
                        if(t==1)to_do.push({"change",{perm[0]}});
                        else to_do.push({"pass",{}});
                    }
                }
                //if(t==1)to_do.push({"change",{perm[0]}});
                //else to_do.push({"pass",{}});
            }
            #if MYDEBUG
            usleep(20000);
            cerr<<flush;
            #endif
            act();
        }
    }
    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;
    }
    pair<int,int> change_success_rate(int state, int fill_mask,int depth=1){
        int maxi=0,ret=0;
        for(int i=0; i<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};
    }

    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]);
                                        cnt++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i=0; i<capacity_comb; ++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);
                }
            }
        }
    }
    void bf(vector<int>&c, vector<vector<short>> &t_table){
        for(int fillbit=1; fillbit<=255; ++fillbit){
            int amount=0;
            for(int b=0; b<8; ++b){
                if((fillbit>>b)&1){
                    amount+=c[b];
                }
            }
            if(lb<=amount && amount<=50){
                t_table[amount].push_back(fillbit);
            }
        }
        for(int i=lb; i<=50; ++i){
            sort(t_table[i].begin(),t_table[i].end());
        }
    }
    void act(){
        if(t==1 || to_do.front().str=="pass" || to_do.front().str =="sell"){
            came[(d-1)/5]++;
            if(to_do.front().str =="sell")sold[(d-1)/5]++;
        }
        if(to_do.front().str =="change")change_cnt++;
        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();
    cerr<<change_cnt<<"\n";
    for(int i=0; i<10; ++i){
        cerr<<i<<' '<<came[i]<<' '<<sold[i]<<endl;
    }

    return 0;
}

Submission Info

Judge Result