結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 nii
|
| 提出日時 | 2018-12-03 23:26:07 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,178 bytes |
| コンパイル時間 | 2,035 ms |
| 実行使用メモリ | 69,620 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2021-07-19 08:15:37 |
| 合計ジャッジ時間 | 35,772 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| 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 | -- | - |
ソースコード
#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];
//
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
for(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,10);
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,10);
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;
}
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;
}