#301210 (C++14) No.5003 物理好きクリッカー

提出ソース
結果

問題	No.5003 物理好きクリッカー
ユーザー	omi_UT
提出日時	2018-12-03 23:30:03
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	12,915 bytes
コンパイル時間	3,500 ms
コンパイル使用メモリ	215,092 KB
実行使用メモリ	25,964 KB
スコア	0
最終ジャッジ日時	2024-04-27 02:43:45
合計ジャッジ時間	351,971 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
//----------------------------おまじない
#pragma GCC optimize ("Ofast")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
//----------------------------
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#define eb(i,j) emplace_back((i),(j))
#include <bits/stdc++.h>
using namespace std;
//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<vvi> vvvi;
typedef long long ll;
typedef vector<ll> vll;
const int mod = 1000000009;

inline unsigned long long rdtsc()
{
#ifdef __amd64
  unsigned long long a, d;
  __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
  return (d << 32) | a;
#else
  unsigned long long x;
  __asm__ volatile ("rdtsc" : "=A" (x));
  return x;
#endif
}

struct SegmentTree {
    int n;
    vi node;

    SegmentTree() : n(0) , node() {}
    SegmentTree(vi v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INT_MAX);
        REP(i,sz) node[i+n-1] = v[i];
        REPN(i,n-2) node[i] = (node[2*i+1] + node[2*i+2]);
    }
    void update(int k, int x){
        k += n-1;
        node[k] = x;
        while(k){
            k = (k-1)/2;
            node[k] = (node[2*k+1] + node[2*k+2]);
        }
    }
    int getsum(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=n;
        if(r<=a || b<=l) return INT_MAX;
        if(a<=l && r<=b) return node[k];
        return ( getsum(a,b,2*k+1,l,(l+r)/2) + getsum(a,b,2*k+2,(l+r)/2,r) );
    }
};

inline double gettime(){return rdtsc()/2593344000.0;}
inline double elapsed(double st){return gettime()-st;}

class Xorshift128 {
private:
  static constexpr unsigned MASK = 0x7FFFFFFF;
  unsigned x = 123456789, y = 987654321, z = 1000000007, w;
public:
  unsigned rnd(){
    unsigned t = x ^ (x << 11);
    x = y; y = z; z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w & MASK;
  }
  Xorshift128(const unsigned seed) : w(seed) {}
};
Xorshift128 prng(21);

const string building[5] = {"hand", "lily", "factory", "casino", "grimoire"};
const string moves[4] = {"click", "buy", "reinforce", "enhclick"};
const ll base_cps[5] = {1,10,120,2000,25000};
const ll base_cost[5] = {150,2000,30000,600000,10000000};
string effects;
vector<double> effectlist(10101);
vector<double> effectrui(10101);

vector<vll> prices(5);

struct Game{
public:
    int gameturn;
    vi moves;
    vi affordables;
    vll cookies;

    ll cookie;
    vll structs;
    vll enhances;
    ll enhclick;

    vll strcosts;
    vll enhcosts;
    ll enhclickcost;

    Game() : gameturn(0), moves(), cookies(), affordables(), cookie(0), enhclick(0), enhclickcost(15){
        structs = vll(5);
        strcosts = {150,2000,30000,600000,10000000};
        enhances = vll(5);
        enhcosts = {1500,20000,300000,6000000,100000000};
        affordables.pb(0);
    }
    Game (const Game& rhs){
        gameturn = rhs.gameturn;
        moves = rhs.moves;
        affordables = rhs.affordables;
        cookies = rhs.cookies;
        cookie = rhs.cookie;
        structs = rhs.structs;
        enhances = rhs.enhances;
        enhclick = rhs.enhclick;
        strcosts = rhs.strcosts;
        enhcosts = rhs.enhcosts;
        enhclickcost = rhs.enhclickcost;
    }

    Game (const Game& rhs, const int ind, const int newmv) : gameturn(0), cookies(), cookie(0), enhclick(0), enhclickcost(15){
        structs = vll(5);
        strcosts = {150,2000,30000,600000,10000000};
        enhances = vll(5);
        enhcosts = {1500,20000,300000,6000000,100000000};

        bool sane = true;
        vi prevmove = rhs.moves;
        prevmove[ind] = newmv;
        moves = vi();
        for (int i=0; i <= ind; i++){
            auto mov = prevmove[i];
            if (mov < 10){
                sane &= affordable(mov);
                spend(mov);
            } else if (mov == 10){
                sane &= (enhclickcost <= cookie);
                enhc();
            } else {
                click();
            }
        }
        if (!sane) {
            cookie = -1145141919LL;
            return;
        }
        FOR(i,ind+1,9900){
            int bo = bestops();
            if ( depr( bo ) && affordable(bo)){
                spend(bo);
            } else if (enhclickcost < (1LL << enhclick) * (10000 - gameturn) * 0.99){
                enhc();
            } else{ 
                click();
            }
        }

        int structno = accumulate(structs.begin(), structs.end(), 0);
        FOR(i,9900,10000-structno) click();
        FOR(i,10000-structno,10000){
            double sellab = -1145141919;
            int ind = -1;
            REP(j,5){
                if (sellab < sellability(j)){
                    sellab = sellability(j);
                    ind = j;
                }
            }
            if (sellab > 0){
                sell(ind);
            } else {
                click();
            }
        }

        
    }

    ll cps(){
        ll ret = 0;
        REP(i,5) ret += structs[i] * ( base_cps[i] << enhances[i] );
        return ret;
    }
    ll turn(){
        ll ret = cps();
        ret *= effectlist[gameturn] == 7 ? 7 : 1;
        cookie += ret;
        cookie += effects[gameturn] == 'B' ? (cookie + 99) / 100 : 0;
        gameturn++;
        cookies.pb(cookie);
        int af = 0;
        REP(i,10){
            af |= (affordable(i) << i); 
        }
        af |= ((enhclickcost <= cookie) << 10 );
        return ret;
    }
    bool affordable(int i){
        return i < 5 ? strcosts[i] <= cookie : enhcosts[i-5] <= cookie;
    }
    ll click(){ // 11
        cookie += (1LL << enhclick);
        moves.pb(11);
        return (1LL << enhclick) + turn();
    }
    ll buy(int i){ // 0-4
        if ( strcosts[i] <= cookie ){
            cookie -= strcosts[i];
            structs[i]++;
            strcosts[i] = prices[i][ structs[i] ];
            moves.pb(i);
        } else {
            return click();
        }
        return turn();
    }
    ll enh(int i){ // 5-9
        if ( enhcosts[i] <= cookie ){
            cookie -= enhcosts[i];
            enhances[i]++;
            enhcosts[i] *= 10;
            moves.pb(i+5);
        } else {
            return click();
        }
        return turn();
    }
    ll enhc(){ // 10
        if ( enhclickcost <= cookie ){
            cookie -= enhclickcost;
            enhclick++;
            enhclickcost *= 10;
            moves.pb(10);
        } else {
            return click();
        }
        return turn();
    }
    ll sell(int i) { //20-24
        if (structs[i]){
            cookie += (prices[i][ structs[i] ]+3)/4;
            strcosts[i] = prices[i][ structs[i] ];
            structs[i]--;
            moves.pb(i+20);
        } else {
            return click();
        }
        return turn();
    }
    ll spend(int i){
        return i < 5 ? buy(i) : enh(i - 5);
    }

    double depturn(int i){
        if (i < 5){
            double d = strcosts[i];
            return d / (base_cps[i] << enhances[i]);
        } else if (i < 10){
            double d = enhcosts[i-5];
            return d / ((base_cps[i-5] << enhances[i-5]) * structs[i-5]);
        }
        return -1;
    }

    double sellability(int i){
        double selpr = (prices[i][ structs[i] ]+3)/4;
        return selpr - (base_cps[i] << enhances[i]) * (10000 - gameturn);
    }

    bool depr(int i){
        double d = depturn(i);
        d *= effects[gameturn] != 'S' ? 1 : 0.9;
        d *= (10000 - gameturn) / effectrui[gameturn];
        return d < (10000 - gameturn);
    }
    
    bool operator< (const Game& rhs) const {
        return cookie < rhs.cookie;
    }
    bool operator> (const Game& rhs) const {
        return cookie > rhs.cookie;
    }
    int bestops(){
        int ret = -1;

        double ratio = -1;
        REP(i,5){
            double delta = (double)( base_cps[i] << enhances[i] ) / strcosts[i];
            if (delta > ratio){
                ratio = delta;
                ret = i;
            }
        }
        REP(i,5){
            double delta = (double)( base_cps[i] << enhances[i] ) * structs[i] / enhcosts[i];
            if (delta > ratio){
                ratio = delta;
                ret = i + 5;
            }
        }

        double r = ret < 5 ? strcosts[ret]: enhcosts[ret-5] ;
        r = (r-cookie)/cps();

        REP(i,10){
            if (depturn(i) < r){
                r = depturn(i); ret = i;
            }
        }
        return ret;
    }

    void output(const bool sub=false){
        char s[114];
        REP(i,10000){
            auto mov = moves[i];
            if (mov < 5) {
                printf("buy %s\n", building[mov%5].c_str());
            } else if (mov < 10){
                printf("reinforce %s\n", building[mov%5].c_str());
            } else if (mov == 10){
                printf("enhclick\n");
            } else if (mov == 11){
                printf("click\n");
            } else {
                printf("sell %s\n", building[mov%5].c_str());
            }
            fflush(stdout);
            if (sub) scanf("%s",s);
        }
    }
    void dump(){
        cerr << gameturn << " " << cps() << "  " << cookie << "  ";
        REP(i,5) cerr << structs[i] << " ";
        REP(i,5) cerr << enhances[i] << " "; 
        cerr << enhclick << endl;
    }

    
};

const string special = "BFS";

void randeffect(){
    int v = 0;
    int t = prng.rnd() % 200;
    effects += 'N' * t;
    effects += special[ prng.rnd()%3 ];
    v += t + 1;

    while( v < 10000){
        t = prng.rnd() % 101 + 99;
        effects += 'N' * t;
        effects += special[ prng.rnd()%3 ];
        v += t + 1;
    }

}

Game gameloop(){
    double st = gettime();
    REP(i,10000){
        char c = effects[i];
        if (c == 'B'){
            effectlist[i] = 1.5;
        } else if (c == 'F'){
            int ii = i + 20;
            for (; i < ii; i++) effectlist[i] = 7;
        } else if (c == 'S'){
            effectlist[i] = 1;
        } else {
            effectlist[i] = 1;
        }
    }
    REPN(i,10000){
        effectrui[i-1] = effectrui[i] + effectlist[i-1];
    }

    Game g = Game();
    REP(i,9900){
        int bo = g.bestops();
        if ( g.depr( bo ) && g.affordable(bo)){
            g.spend(bo);
        } else if (g.enhclickcost < (1LL << g.enhclick) * (10000 - g.gameturn) * 0.99){
            g.enhc();
        } else{ 
            g.click();
        }
        // if (i % 10 == 0 ) {
        //     cerr << bo << " " << g.depturn(bo) << endl;
        //     g.dump();
        // }
    }
    int structno = accumulate(g.structs.begin(), g.structs.end(), 0);
    FOR(i,9900,10000-structno) g.click();
    FOR(i,10000-structno,10000){
        double sellab = -1145141919;
        int ind = -1;
        REP(j,5){
            if (sellab < g.sellability(j)){
                sellab = g.sellability(j);
                ind = j;
            }
        }
        if (sellab > 0){
            g.sell(ind);
        } else {
            g.click();
        }
    }
    cerr << g.cookie << endl; 

    const double limittime = 9.0;
    const double startTemp = 5;
    double tim = elapsed(st);
    int ctr = 0;
    const int oneloop = 1000;

    while( tim < limittime ){
        REP(_,oneloop){
            int idx = prng.rnd() % 9000;
            if (!g.affordables[idx]) continue;

            int bin = __builtin_popcount(g.affordables[idx]);
            int change = g.moves[idx] == 11 ? prng.rnd() % 11 : 11;

            Game gi = Game(g, idx, change);
            if (gi.cookie < 0) continue;

            double dscore = gi.cookie - g.cookie;
            dscore *= 3e-8;
            double temper = startTemp * (1.0 -  tim / limittime * tim / limittime);
            double prob = exp( dscore/temper);

            
            bool exch = prob * (double)UINT_MAX > (double)(prng.rnd());
            if (exch) {
                
                g = gi;
            }    
        }
        tim = elapsed(st);
        ctr+=oneloop;
        cerr << " " << ctr << " " << g.cookie << "\r"; 

    }
    cerr << "                                     \r";
    cerr << ctr << " " << g.cookie << endl; 

    return g; 
}

void test(){
    ll v = 0;
    REP(i,32){
        prng = Xorshift128(i);
        effects = "";
        randeffect();
        v += gameloop().cookie;
    }
    cerr << v << endl;
}

void exec(){
    int v; cin >> v;
    cin >> effects;

    auto g = gameloop();
    g.output(true);
}

int main(){
    REP(i,5){
        ll pr = base_cost[i];
        REP(j,100){
            prices[i].pb(pr);
            pr = (pr*6 + 4 )/ 5;
        }
    }
    //test();
    exec();
}
yukicoder

結果

テストケース

ソースコード
