結果
問題 | No.5003 物理好きクリッカー |
ユーザー | omi_UT |
提出日時 | 2018-12-13 18:09:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 14,538 bytes |
コンパイル時間 | 4,903 ms |
コンパイル使用メモリ | 261,024 KB |
実行使用メモリ | 33,808 KB |
スコア | 0 |
最終ジャッジ日時 | 2024-04-27 02:44:40 |
合計ジャッジ時間 | 27,376 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
ソースコード
//----------------------------おまじない #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 vector<char> vc; 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 unsigned long long ull; typedef vector<ll> vll; typedef vector<ull> vull; 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 } 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); ll powll(ll base,ll power){ ll ans = 1; while (power){ if (power&1) ans = (base*ans); base = (base*base); power >>= 1; } return ans; } const string building[5] = {"hand", "lily", "factory", "casino", "grimoire"}; 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),enhprices(5); double dismiss = 0.0; double coef_base = 0.6; double coef_thres = 7000; double startTemp = 5.0; double temppow = 2.0; struct Game{ public: int gameturn; vi moves; vll cookies; vull states; ll cookie; vll structs; vll enhances; ll enhclick; ll enhclickcost; Game() : gameturn(0), moves(), cookies(), states(), cookie(0), enhclick(0), enhclickcost(15){ structs = vll(5); enhances = vll(5); } Game (const Game& rhs) = default; Game (const Game& rhs, const int ind, const int newmv) { structs = vll(5); enhances = vll(5); cookie = rhs.cookies[ind-1]; unpack(rhs.states[ind-1]); gameturn = ind; enhclickcost = 15 * powll(10, enhclick); if (newmv < 10 && !affordable(newmv)){ cookie = -1; return; } else if (newmv == 10 && (enhclickcost > cookie)){ cookie = -1; return; } moves = vi( rhs.moves.begin(), rhs.moves.begin()+ind ); states = vull( rhs.states.begin(), rhs.states.begin()+ind ); cookies = vll( rhs.cookies.begin(), rhs.cookies.begin()+ind ); if (newmv < 10){ spend(newmv); } else if (newmv == 10){ enhc(); } else { click(); } prng.rnd(); FOR(i,ind+1,9900){ int bo = bestops(); if ( depr( bo )){ while(! affordable(bo) ) {click(); i++;} spend(bo); } else if (enhclickcost < (1LL << enhclick) * (10000 - gameturn)){ enhc(); } else{ for(; i<9900; i++) click(); } } FOR(i,9900,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(); } } } bool less_state( const Game& rhs){ return structs == rhs.structs && enhances == rhs.enhances && cookie <= rhs.cookie && enhclick <= rhs.enhclick ; } ll enhcosts(int i){ ll base = enhprices[i][enhances[i]]; return base * (gameturn && effects[gameturn-1] == 'S' ? 0.9 : 1); } ll strcosts(int i){ ll base = prices[i][structs[i]]; return base * (gameturn && effects[gameturn-1] == 'S' ? 0.9 : 1); } ll cps() const { ll ret = 0; REP(i,5) ret += structs[i] * ( base_cps[i] << enhances[i] ); return ret; } ull pack(){ ull ret = 0; REP(i,5) ret |= (structs[i] << (i*8)); REP(i,5) ret |= (enhances[i] << (i*4 + 40)); return ret | (enhclick << 60); } void unpack(ull pc){ REP(i,5) structs[i] = (pc >> (i*8)) & 0xFF; REP(i,5) enhances[i] = (pc >> (i*4 + 40)) & 0x0F; enhclick = (pc >> 60) & 0x0F; } ll turn(bool packing=true){ ll ret = cps(); ret *= effectlist[gameturn]; cookie += ret; cookie += effects[gameturn] == 'B' ? (cookie + 99) / 100 : 0; cookies.pb(cookie); states.pb( packing ? pack() : states.back() ); gameturn++; return ret; } bool affordable(int i){ return i < 5 ? strcosts(i) <= cookie : enhcosts(i-5) <= cookie; } ll click(){ // 11 cookie += (1LL << enhclick) * (effectlist[gameturn]); moves.pb(11); // return (1LL << enhclick) * (effectlist[gameturn]) + turn(!gameturn); return turn(!gameturn); } ll buystr(int i){ // 0-4 if ( strcosts(i) <= cookie ){ cookie -= strcosts(i); structs[i]++; moves.pb(i); } else { return click(); } return turn(); } ll enh(int i){ // 5-9 if ( structs[i] && enhcosts(i) <= cookie ){ cookie -= enhcosts(i); enhances[i]++; 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]-1 ]+3)/4; structs[i]--; moves.pb(i+20); } else { return click(); } return turn(); } ll spend(int i){ return i < 5 ? buystr(i) : enh(i - 5); } double depturn(int i){ if (i < 5){ double d = strcosts(i); d /= (base_cps[i] << enhances[i]); return d; } else if (i < 10){ double d = enhcosts(i-5); d /= ((base_cps[i-5] << enhances[i-5]) * structs[i-5]); return d; } return -1; } double sellability(int i){ if (!structs[i]) return -1; double selpr = (prices[i][ structs[i]-1]+3)/4; return selpr - (base_cps[i] << enhances[i]) * effectrui[gameturn]; } double coef(){ return gameturn < coef_thres ? ((double)gameturn / coef_thres * (1 - coef_base)) + coef_base : 1; } bool depr(int i){ double d = depturn(i); d *= (10000 - gameturn) / effectrui[gameturn]; //d *= coef(); return d < (10000 - gameturn); } bool operator< (const Game& rhs) const { return cookie + cps() * (10000-gameturn) < rhs.cookie + rhs.cps() * (10000-gameturn); } bool operator> (const Game& rhs) const { return cookie > rhs.cookie; } int bestops(){ int ret = -1; double ratio = -1; REP(i,5){ double strprod = ( base_cps[i] << enhances[i] ); double delta = strprod / strcosts(i); if (delta > ratio){ ratio = delta; ret = i; } delta = strprod * 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; // } // } assert(ret >= 0); return ret; } void output(const bool sub=false){ char s[114]; int maxi = 10000; int lasc = 0; REPN(inv,10000){ if (moves[inv] == 11){ lasc++; } else { break; } } REP(i,maxi){ 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 { while(lasc){ printf("click\n"); fflush(stdout); if (sub) scanf("%s",s); maxi--; lasc--; } 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; } void simulate(){ Game cp; REP(i,10000){ auto mov = moves[i]; if (mov < 10){ cp.spend(mov); } else if (mov == 10){ cp.enhc(); } else if (mov == 11){ cp.click(); } else{ cp.sell(mov%5); } cerr << cp.cookie << endl; } } }; const string special = "BFS"; void randeffect(){ int v = 0; int t = prng.rnd() % 200; REP(i,t) effects += 'N'; effects += special[ prng.rnd()%3 ]; v += t + 1; while( v < 10000){ t = prng.rnd() % 101 + 99; REP(i,t) effects += 'N'; 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; } else if (c == 'F'){ int ii = i + 21; i++; 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(); //bool buy = dismiss * UINT_MAX < prng.rnd(); if ( g.depr( bo ) && g.affordable(bo)){ g.spend(bo); } else if (g.enhclickcost < (1LL << g.enhclick) * (10000 - g.gameturn)){ 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.5; double tim = elapsed(st); int ctr = 0; const int oneloop = 100; while( tim < limittime ){ REP(_,oneloop){ int idx = prng.rnd() % 8000 + 100; //int change = g.moves[idx] == 11 ? prng.rnd() % 11 : 11; int change = prng.rnd() % 12; if (change == g.moves[idx]) continue; Game gi = Game(g, idx, change); if (gi.cookie < 0) continue; double dscore = (gi.cookie - g.cookie); dscore *= 1e-8; double temper = startTemp * (1.0 - 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; } long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;} void test(int offset=0){ ll v = 0; REP(i,32){ prng = Xorshift128(i + offset); effects = ""; randeffect(); v += gameloop().cookie; //break; } cout << v << endl; } void exec(){ int v; cin >> v; cin >> effects; auto g = gameloop(); g.output(true); //cerr << g.cookie << endl; //g.simulate(); } void make_sample(int rnd=21){ cout << 10000 << endl; prng = Xorshift128(rnd); randeffect(); cout << effects << endl; REP(i,10000) cout << "ok" << endl; } int main(int argc, char *argv[]){ ios::sync_with_stdio(false); //dismiss = 0.0; //atof(argv[1]); // 0.0 coef_base = 0.6; //atof(argv[2]); // 0.6 coef_thres = 8280; //atof(argv[3]); //7000 startTemp = 4; //atof(argv[4]); //5.0 //temppow = 0.04686; //atof(argv[5]); //2.0 //{'base': 0.6004643314155524, 'pow': 0.046862762704473385, 'temp': 45.93752027988493, 'thres': 8279.719154386894} REP(i,5){ ll pr = base_cost[i]; REP(j,100){ prices[i].pb(pr); pr = llceil(pr*6 ,5); } } REP(i,5){ ll pr = base_cost[i] * 10; REP(j,15){ enhprices[i].pb(pr); pr *= 10; } } //test(114514); exec(); //make_sample(); }