結果
| 問題 |
No.5003 物理好きクリッカー
|
| コンテスト | |
| ユーザー |
 omi_UT
|
| 提出日時 | 2018-12-13 12:01:59 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 16,709 bytes |
| コンパイル時間 | 5,242 ms |
| コンパイル使用メモリ | 245,832 KB |
| 実行使用メモリ | 33,936 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-04-27 02:44:27 |
| 合計ジャッジ時間 | 27,823 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 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){
gameturn = rhs.gameturn;
moves = rhs.moves;
cookies = rhs.cookies;
states = rhs.states;
cookie = rhs.cookie;
structs = rhs.structs;
enhances = rhs.enhances;
enhclick = rhs.enhclick;
enhclickcost = rhs.enhclickcost;
}
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 ) && affordable(bo)){
spend(bo);
} else if (enhclickcost < (1LL << enhclick) * (9900 - gameturn)){
enhc();
} else{
click();
}
}
int structno = accumulate(structs.begin(), structs.end(), 0);
FOR(i,9900,10000-structno) click();
FOR(i,10000-structno,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(){
ll ret = cps();
ret *= effectlist[gameturn] == 7 ? 7 : 1;
cookie += ret;
cookie += effects[gameturn] == 'B' ? (cookie + 99) / 100 : 0;
gameturn++;
cookies.pb(cookie);
states.pb(pack());
return ret;
}
bool affordable(int i){
return i < 5 ? strcosts(i) <= cookie : enhcosts(i-5) <= cookie;
}
ll click(){ // 11
cookie += (1LL << enhclick) * (effectlist[gameturn] == 7 ? 7 : 1);
moves.pb(11);
return (1LL << enhclick) * (effectlist[gameturn] == 7 ? 7 : 1) + turn();
}
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] ]+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){
double selpr = (prices[i][ structs[i] ]+3)/4;
return selpr - (base_cps[i] << enhances[i]) * (10000 - 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 delta = (double)( base_cps[i] << enhances[i] ) / strcosts(i);
if (delta > ratio){
ratio = delta;
ret = i;
}
}
REP(i,5){
double delta = (double)( base_cps[i] << enhances[i] ) * 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,9999){
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 {
REP(j,lasc){
printf("click\n");
fflush(stdout);
if (sub) scanf("%s",s);
maxi--;
}
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.5;
} 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) * 0.99){
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;
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 - pow(tim / limittime,temppow ) );
//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;
}
Game beam(){
double st = gettime();
vector<pair<int,char>> veff;
REP(i,10000){
char c = effects[i];
if (c != 'N') veff.eb(i,c);
}
priority_queue<Game> Bstate;
Bstate.push(Game());
int wid = 1000;
int prevturn = 0;
REP(t,veff.size()*2){
int nowturn = veff[t/2].first + (t&1);
int deltaturn = nowturn - prevturn -1;
priority_queue<Game> Bnewstate;
Game prevstate;
REP(i,wid){
if (Bstate.empty()) break;
auto nowstate = Bstate.top();
Bstate.pop();
if ((t/2) && nowstate.less_state(prevstate)){
i--;
continue;
} else {
prevstate = nowstate;
}
REP(mov, 10){
if ( nowstate.affordable(mov) ){
auto nextstate = nowstate;
nextstate.spend(mov);
REP(j,deltaturn) nextstate.click();
if (! Bnewstate.empty()){
auto nexttop = Bnewstate.top();
if (nextstate.less_state(nexttop)) continue;
}
Bnewstate.push(nextstate);
}
}
if (nowstate.enhclickcost <= nowstate.cookie){
auto nextstate = nowstate;
nextstate.enhc();
REP(j,deltaturn) nextstate.click();
if ( Bnewstate.empty() || !nextstate.less_state(Bnewstate.top())){
Bnewstate.push(nextstate);
}
}
REP(j,deltaturn + 1) nowstate.click();
if ( Bnewstate.empty() || !nowstate.less_state(Bnewstate.top())){
Bnewstate.push(nowstate);
}
}
Bstate = Bnewstate;
prevturn = nowturn;
}
cerr << elapsed(st) << " " << Bstate.top().cookie << endl;
return Bstate.top();
}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
void test(){
ll v = 0;
REP(i,32){
prng = Xorshift128(i);
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[]){
//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 = 45.98; //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();
exec();
//make_sample();
}