結果
問題 | No.5003 物理好きクリッカー |
ユーザー |
![]() |
提出日時 | 2018-12-02 22:09:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,177 ms / 10,000 ms |
コード長 | 7,068 bytes |
コンパイル時間 | 2,193 ms |
実行使用メモリ | 23,712 KB |
スコア | 436,813,875 |
平均クエリ数 | 10000.00 |
最終ジャッジ日時 | 2021-07-19 07:58:33 |
合計ジャッジ時間 | 42,991 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;vector<long long> efficiency(6);vector<vector<long long>> buyprice(6,vector<long long>(10001));vector<vector<long long>> sellprice(6,vector<long long>(10001));vector<vector<long long>> reinforceprice(6,vector<long long>(10001));//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==right.future?left.cookie<right.cookie:left.future<right.future;}//const int beam_width=1;state BeamSearch(){priority_queue<state> nowstate;state nii;nowstate.push(nii);int fever=0;bool sale=false;for(int i=0;i<n;++i){// if(i%1000==0){// cerr<<"BeamSearch begin"<<" "<<i<<" "<<nowstate.top().cookie<<endl;// }priority_queue<state> nextstate;for(int j=0;j<beam_width&&!nowstate.empty();++j){queue<state> nexstate;state now=nowstate.top();nowstate.pop();//action//clicknow.cookie+=now.inst_cn[0]*(1LL<<now.inst_lv[0]);now.order.push_back({0,0});nexstate.push(now);now.order.pop_back();now.cookie-=now.inst_cn[0]*(1LL<<now.inst_lv[0]);//buyfor(int k=1;k<6;++k){if(k>=2&&i<=1000){break;}if(now.cookie>=buyprice[k][now.inst_cn[k]]){now.cookie-=(sale?floor(buyprice[k][now.inst_cn[k]]*0.9):buyprice[k][now.inst_cn[k]]);now.inst_cn[k]++;now.future+=(i<=9900)*efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*100;now.order.push_back({1,k});nexstate.push(now);now.order.pop_back();now.future-=(i<=9900)*efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*100;now.inst_cn[k]--;now.cookie+=(sale?floor(buyprice[k][now.inst_cn[k]]*0.9):buyprice[k][now.inst_cn[k]]);}}//sellfor(int k=1;k<6;++k){if(i<=9900){break;}if(now.inst_cn[k]){now.cookie+=sellprice[k][now.inst_cn[k]];now.inst_cn[k]--;now.order.push_back({2,k});nexstate.push(now);now.order.pop_back();now.inst_cn[k]++;now.cookie-=sellprice[k][now.inst_cn[k]];}}//reinforcefor(int k=1;k<6;++k){if(i<3000){break;}if(now.inst_cn[k]&&now.cookie>=reinforceprice[k][now.inst_lv[k]]){now.cookie-=(sale?floor(reinforceprice[k][now.inst_lv[k]]*0.9):reinforceprice[k][now.inst_lv[k]]);now.inst_lv[k]++;now.future+=(i<=9900)*efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*100;now.order.push_back({3,k});nexstate.push(now);now.order.pop_back();now.future-=(i<=9900)*efficiency[k]*now.inst_cn[k]*(1LL<<now.inst_lv[k])*100;now.inst_lv[k]--;now.cookie+=(sale?floor(reinforceprice[k][now.inst_lv[k]]*0.9):reinforceprice[k][now.inst_lv[k]]);}}//enhclickif(now.cookie>=reinforceprice[0][now.inst_lv[0]]){now.cookie-=(sale?floor(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]);now.order.push_back({4,0});nexstate.push(now);now.order.pop_back();now.future-=efficiency[0]*now.inst_cn[0]*(1LL<<now.inst_lv[0]);now.inst_lv[0]--;now.cookie+=(sale?floor(reinforceprice[0][now.inst_lv[0]]*0.9):reinforceprice[0][now.inst_lv[0]]);}//producewhile(!nexstate.empty()){state mow=nexstate.front();nexstate.pop();for(int k=1;k<6;k++){mow.cookie+=efficiency[k]*mow.inst_cn[k]*(1LL<<mow.inst_lv[k])*(fever>0?7:1);}if(s[i]=='B'){mow.cookie+=floor(mow.cookie*0.01);}(mow.future*=(n-i-1))/=(n-i);nextstate.push(mow);}}//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;// cerr<<"input ok"<<endl;}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]=floor(buyprice[i][j]*6/5);}}sellprice[1][1]=150/4;sellprice[2][1]=2000/4;sellprice[3][1]=30000/4;sellprice[4][1]=600000/4;sellprice[5][1]=10000000/4;for(int i=1;i<6;++i){for(int j=2;j<n;++j){sellprice[i][j]=floor(buyprice[i][j-1]/4);}}reinforceprice[0][0]=15;reinforceprice[1][0]=1500;reinforceprice[5][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=BeamSearch().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;}