結果

問題 No.5003 物理好きクリッカー
ユーザー niinii
提出日時 2018-12-05 18:11:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,662 ms / 10,000 ms
コード長 7,606 bytes
コンパイル時間 2,207 ms
実行使用メモリ 27,780 KB
スコア 100,548,584,283
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 08:50:00
合計ジャッジ時間 127,641 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,401 ms
27,164 KB
testcase_01 AC 3,380 ms
26,980 KB
testcase_02 AC 3,468 ms
27,040 KB
testcase_03 AC 3,391 ms
26,704 KB
testcase_04 AC 3,442 ms
26,920 KB
testcase_05 AC 3,474 ms
26,448 KB
testcase_06 AC 3,573 ms
26,860 KB
testcase_07 AC 3,500 ms
26,712 KB
testcase_08 AC 3,563 ms
26,804 KB
testcase_09 AC 3,559 ms
26,884 KB
testcase_10 AC 3,617 ms
27,116 KB
testcase_11 AC 3,539 ms
26,888 KB
testcase_12 AC 3,384 ms
26,724 KB
testcase_13 AC 3,444 ms
26,612 KB
testcase_14 AC 3,445 ms
26,848 KB
testcase_15 AC 3,479 ms
26,888 KB
testcase_16 AC 3,464 ms
26,984 KB
testcase_17 AC 3,662 ms
26,536 KB
testcase_18 AC 3,531 ms
26,736 KB
testcase_19 AC 3,423 ms
27,200 KB
testcase_20 AC 3,551 ms
26,668 KB
testcase_21 AC 3,558 ms
27,780 KB
testcase_22 AC 3,517 ms
26,752 KB
testcase_23 AC 3,513 ms
26,780 KB
testcase_24 AC 3,457 ms
26,832 KB
testcase_25 AC 3,572 ms
26,820 KB
testcase_26 AC 3,605 ms
27,224 KB
testcase_27 AC 3,565 ms
26,788 KB
testcase_28 AC 3,479 ms
26,896 KB
testcase_29 AC 3,387 ms
26,916 KB
testcase_30 AC 3,540 ms
26,840 KB
testcase_31 AC 3,597 ms
26,636 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 nextsale[10001];
//
struct action{
	int type=-1;//0:click.1:buy,2:sell,3:reinforce,4:enhclick
	int 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:grimoire
	int 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();
		//action
			state mem=now;
			//click
			now.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;
			//buy
			bool f=false;
			for(int k=5;k>=1;--k){
				if(i<2000){
					f=!nextsale[i]*efficiency[k]*(1LL<<now.inst_lv[k])>ceil((double)buyprice[k][now.inst_cn[k]]*0.1);
				}else{
					if(f){
						if(k!=2){
							continue;
						}else{
							f=false;
						}
					}
					f=!(k==2?now.inst_cn[2]<=15:1);
				}
				if(now.cookie>=(sale?ceil((double)buyprice[k][now.inst_cn[k]]*0.9):buyprice[k][now.inst_cn[k]])&&!f){
					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;
				}
			}
			//sell
			for(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;
				}
			}
			//reinforce
			for(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;
				}
			}
			//enhclick
			if(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;
			}
		}
		//effect
		if(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;
	int now=0;
	for(int i=n-1;i>=0;i--){
		if(s[i]=='S'){
			now=0;
		}else{
			now++;
		}
		nextsale[i]=now;
	}
}
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;
}
0