結果
問題 | No.5003 物理好きクリッカー |
ユーザー |
![]() |
提出日時 | 2018-12-03 23:30:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 32 |
ソースコード
//----------------------------おまじない#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 __amd64unsigned long long a, d;__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));return (d << 32) | a;#elseunsigned 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(){ // 11cookie += (1LL << enhclick);moves.pb(11);return (1LL << enhclick) + turn();}ll buy(int i){ // 0-4if ( 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-9if ( enhcosts[i] <= cookie ){cookie -= enhcosts[i];enhances[i]++;enhcosts[i] *= 10;moves.pb(i+5);} else {return click();}return turn();}ll enhc(){ // 10if ( enhclickcost <= cookie ){cookie -= enhclickcost;enhclick++;enhclickcost *= 10;moves.pb(10);} else {return click();}return turn();}ll sell(int i) { //20-24if (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();}