結果
問題 | No.5003 物理好きクリッカー |
ユーザー |
![]() |
提出日時 | 2018-12-03 23:09:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,852 ms / 10,000 ms |
コード長 | 7,176 bytes |
コンパイル時間 | 2,266 ms |
実行使用メモリ | 27,872 KB |
スコア | 100,548,584,283 |
平均クエリ数 | 10000.00 |
最終ジャッジ日時 | 2021-07-19 08:16:34 |
合計ジャッジ時間 | 131,672 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;//const int64_t CYCLES_PER_SEC=2800000000;struct Timer{int64_t start;Timer(){reset();}void reset(){start=getcycle();}void plus(double a){start-=(a*CYCLES_PER_SEC);}inline double get(){return (double)(getcycle()-start)/CYCLES_PER_SEC;}inline int64_t getcycle(){uint32_t low,high;__asm__ volatile ("rdtsc":"=a"(low),"=d"(high));return ((int64_t)low)|((int64_t)high<<32);}};int n;string s;long long efficiency[6];long long buyprice[6][10001];long long sellprice[6][10001];long long reinforceprice[6][10001];int Fever[100000];//struct action{int type=-1;//0:click.1:buy,2:sell,3:reinforce,4:enhclickint idx=-1;//0:click,1:hand,2:lily,3:factory,4:casino,5:grimoire};struct state{long long cookie=0;long long future=0;vector<action> order;int inst_cn[6]={1,0,0,0,0,0};//0:click,1:hand,2:lily,3:factory,4:casino,5:grimoireint inst_lv[6]={0,0,0,0,0,0};//0:click,1:hand,2:lily,3:factory,4:casino,5:grimoire};inline bool operator<(const state&left,const state&right){return left.future+left.cookie<right.future+right.cookie;}//int beam_width=1;state greedy(){priority_queue<state> nowstate;state nii;nowstate.push(nii);int fever=0;bool sale=false;long long ma=0;for(int i=0;i<n;++i){ma=max(ma,nowstate.top().cookie);if(i%1000==0){cerr<<"Greedy begin"<<" "<<i<<" "<<ma<<endl;for(int i=0;i<6;i++){cerr<<nowstate.top().inst_cn[i]<<" ";}cerr<<endl;for(int i=0;i<6;i++){cerr<<nowstate.top().inst_lv[i]<<" ";}cerr<<endl;}priority_queue<state> nextstate;for(int j=0;j<beam_width&&!nowstate.empty();++j){queue<state> nexstate;state now=nowstate.top();nowstate.pop();//actionstate mem=now;//clicknow.cookie+=now.inst_cn[0]*(1LL<<now.inst_lv[0]);now.order.push_back({0,0});for(int k=1;k<6;k++){now.cookie+=efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*(fever>0?7:1);}if(s[i]=='B'){now.cookie+=ceil((double)now.cookie*0.01);}nextstate.push(now);now=mem;//buyfor(int k=1;k<6;++k){if(now.cookie>=(sale?ceil((double)buyprice[k][now.inst_cn[k]]*0.9):buyprice[k][now.inst_cn[k]])){now.cookie-=(sale?ceil((double)buyprice[k][now.inst_cn[k]]*0.9):buyprice[k][now.inst_cn[k]]);now.inst_cn[k]++;now.future=efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*(n-i);now.order.push_back({1,k});for(int l=1;l<6;++l){now.cookie+=efficiency[l]*now.inst_cn[l]*(1LL<<now.inst_lv[l])*(fever>0?7:1);}if(s[i]=='B'){now.cookie+=ceil((double)now.cookie*0.01);}if(k==5){beam_width++;beam_width=min(beam_width,3);now.future*=7;}nextstate.push(now);now=mem;}}//sellfor(int k=1;k<6;++k){if(i<=9990){break;}if(now.inst_cn[k]>0){now.cookie+=sellprice[k][now.inst_cn[k]];now.inst_cn[k]--;now.order.push_back({2,k});for(int l=1;l<6;++l){now.cookie+=efficiency[l]*now.inst_cn[l]*(1LL<<now.inst_lv[l])*(fever>0?7:1);}if(s[i]=='B'){now.cookie+=ceil((double)now.cookie*0.01);}nextstate.push(now);now=mem;}}//reinforcefor(int k=1;k<6;++k){if(now.inst_cn[k]>0&&now.cookie>=(sale?ceil((double)reinforceprice[k][now.inst_lv[k]]*0.9):reinforceprice[k][now.inst_lv[k]])){now.cookie-=(sale?ceil((double)reinforceprice[k][now.inst_lv[k]]*0.9):reinforceprice[k][now.inst_lv[k]]);now.inst_lv[k]++;now.future=efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*(n-i);now.order.push_back({3,k});for(int l=1;l<6;++l){now.cookie+=efficiency[l]*now.inst_cn[l]*(1LL<<now.inst_lv[l])*(fever>0?7:1);}if(s[i]=='B'){now.cookie+=ceil((double)now.cookie*0.01);}now.future*=k;if(k==5){beam_width++;beam_width=min(beam_width,3);now.future*=10;}nextstate.push(now);now=mem;}}//enhclickif(now.cookie>=(sale?ceil((double)reinforceprice[0][now.inst_lv[0]]*0.9):reinforceprice[0][now.inst_lv[0]])){now.cookie-=(sale?ceil((double)reinforceprice[0][now.inst_lv[0]]*0.9):reinforceprice[0][now.inst_lv[0]]);now.inst_lv[0]++;now.future=efficiency[0]*now.inst_cn[0]*(1LL<<now.inst_lv[0])*(n-i);now.order.push_back({4,0});for(int l=1;l<6;++l){now.cookie+=efficiency[l]*now.inst_cn[l]*(1LL<<now.inst_lv[l])*(fever>0?7:1);}if(s[i]=='B'){now.cookie+=ceil((double)now.cookie*0.01);}nextstate.push(now);now=mem;}}//effectif(s[i]=='F'){fever=20;}else if(fever>0){fever--;}if(s[i]=='S'){sale=true;}else if(sale){sale=false;}nowstate=nextstate;}cerr<<nowstate.top().cookie<<endl;return nowstate.top();}//void input(){// ifstream cin("input.txt");cin>>n>>s;}void setprice(){efficiency[0]=1;efficiency[1]=1;efficiency[2]=10;efficiency[3]=120;efficiency[4]=2000;efficiency[5]=25000;buyprice[1][0]=150;buyprice[2][0]=2000;buyprice[3][0]=30000;buyprice[4][0]=600000;buyprice[5][0]=10000000;for(int i=1;i<6;++i){for(int j=0;j<n;++j){buyprice[i][j+1]=ceil((double)buyprice[i][j]*6/5);}}for(int i=1;i<6;++i){for(int j=1;j<n;++j){sellprice[i][j]=ceil((double)buyprice[i][j-1]/4);}}reinforceprice[0][0]=15;reinforceprice[1][0]=1500;reinforceprice[2][0]=20000;reinforceprice[3][0]=300000;reinforceprice[4][0]=6000000;reinforceprice[5][0]=100000000;for(int i=0;i<6;i++){for(int j=0;j<20;j++){reinforceprice[i][j+1]=reinforceprice[i][j]*10;}}}void output(){// ofstream cout("output.txt");vector<action> nii=greedy().order;for(int i=0;i<n;i++){if(nii[i].type==0){cout<<"click"<<endl;}else if(nii[i].type==1){if(nii[i].idx==1){cout<<"buy hand"<<endl;}else if(nii[i].idx==2){cout<<"buy lily"<<endl;}else if(nii[i].idx==3){cout<<"buy factory"<<endl;}else if(nii[i].idx==4){cout<<"buy casino"<<endl;}else{cout<<"buy grimoire"<<endl;}}else if(nii[i].type==2){if(nii[i].idx==1){cout<<"sell hand"<<endl;}else if(nii[i].idx==2){cout<<"sell lily"<<endl;}else if(nii[i].idx==3){cout<<"sell factory"<<endl;}else if(nii[i].idx==4){cout<<"sell casino"<<endl;}else{cout<<"sell grimoire"<<endl;}}else if(nii[i].type==3){if(nii[i].idx==1){cout<<"reinforce hand"<<endl;}else if(nii[i].idx==2){cout<<"reinforce lily"<<endl;}else if(nii[i].idx==3){cout<<"reinforce factory"<<endl;}else if(nii[i].idx==4){cout<<"reinforce casino"<<endl;}else{cout<<"reinforce grimoire"<<endl;}}else{cout<<"enhclick"<<endl;}string hoge;cin>>hoge;}}//int main(){Timer nii;input();setprice();output();cerr<<nii.get()<<endl;return 0;}