結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 omi_UT
|
| 提出日時 | 2018-12-03 23:30:03 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 12,915 bytes |
| コンパイル時間 | 1,825 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2021-07-19 08:15:42 |
| 合計ジャッジ時間 | 2,348 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr.h:148,
from /usr/local/gcc7/include/c++/10.2.0/ext/atomicity.h:35,
from /usr/local/gcc7/include/c++/10.2.0/bits/ios_base.h:39,
from /usr/local/gcc7/include/c++/10.2.0/ios:42,
from /usr/local/gcc7/include/c++/10.2.0/istream:38,
from /usr/local/gcc7/include/c++/10.2.0/sstream:38,
from /usr/local/gcc7/include/c++/10.2.0/complex:45,
from /usr/local/gcc7/include/c++/10.2.0/ccomplex:39,
from /usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:54,
from main.cpp:14:
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:102:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:102:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:103:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:103:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:104:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:104:1: エラー: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/local/gcc7/include/c++/10.2.0/x86_64-pc-linux-gnu/bits/gthr-default.h:106
ソースコード
//----------------------------おまじない
#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 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 vector<ll> vll;
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
}
struct SegmentTree {
int n;
vi node;
SegmentTree() : n(0) , node() {}
SegmentTree(vi v) {
int sz = v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1, INT_MAX);
REP(i,sz) node[i+n-1] = v[i];
REPN(i,n-2) node[i] = (node[2*i+1] + node[2*i+2]);
}
void update(int k, int x){
k += n-1;
node[k] = x;
while(k){
k = (k-1)/2;
node[k] = (node[2*k+1] + node[2*k+2]);
}
}
int getsum(int a, int b, int k=0, int l=0, int r=-1){
if(r<0) r=n;
if(r<=a || b<=l) return INT_MAX;
if(a<=l && r<=b) return node[k];
return ( getsum(a,b,2*k+1,l,(l+r)/2) + getsum(a,b,2*k+2,(l+r)/2,r) );
}
};
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);
const string building[5] = {"hand", "lily", "factory", "casino", "grimoire"};
const string moves[4] = {"click", "buy", "reinforce", "enhclick"};
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);
struct Game{
public:
int gameturn;
vi moves;
vi affordables;
vll cookies;
ll cookie;
vll structs;
vll enhances;
ll enhclick;
vll strcosts;
vll enhcosts;
ll enhclickcost;
Game() : gameturn(0), moves(), cookies(), affordables(), cookie(0), enhclick(0), enhclickcost(15){
structs = vll(5);
strcosts = {150,2000,30000,600000,10000000};
enhances = vll(5);
enhcosts = {1500,20000,300000,6000000,100000000};
affordables.pb(0);
}
Game (const Game& rhs){
gameturn = rhs.gameturn;
moves = rhs.moves;
affordables = rhs.affordables;
cookies = rhs.cookies;
cookie = rhs.cookie;
structs = rhs.structs;
enhances = rhs.enhances;
enhclick = rhs.enhclick;
strcosts = rhs.strcosts;
enhcosts = rhs.enhcosts;
enhclickcost = rhs.enhclickcost;
}
Game (const Game& rhs, const int ind, const int newmv) : gameturn(0), cookies(), cookie(0), enhclick(0), enhclickcost(15){
structs = vll(5);
strcosts = {150,2000,30000,600000,10000000};
enhances = vll(5);
enhcosts = {1500,20000,300000,6000000,100000000};
bool sane = true;
vi prevmove = rhs.moves;
prevmove[ind] = newmv;
moves = vi();
for (int i=0; i <= ind; i++){
auto mov = prevmove[i];
if (mov < 10){
sane &= affordable(mov);
spend(mov);
} else if (mov == 10){
sane &= (enhclickcost <= cookie);
enhc();
} else {
click();
}
}
if (!sane) {
cookie = -1145141919LL;
return;
}
FOR(i,ind+1,9900){
int bo = bestops();
if ( depr( bo ) && affordable(bo)){
spend(bo);
} else if (enhclickcost < (1LL << enhclick) * (10000 - gameturn) * 0.99){
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();
}
}
}
ll cps(){
ll ret = 0;
REP(i,5) ret += structs[i] * ( base_cps[i] << enhances[i] );
return ret;
}
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);
int af = 0;
REP(i,10){
af |= (affordable(i) << i);
}
af |= ((enhclickcost <= cookie) << 10 );
return ret;
}
bool affordable(int i){
return i < 5 ? strcosts[i] <= cookie : enhcosts[i-5] <= cookie;
}
ll click(){ // 11
cookie += (1LL << enhclick);
moves.pb(11);
return (1LL << enhclick) + turn();
}
ll buy(int i){ // 0-4
if ( strcosts[i] <= cookie ){
cookie -= strcosts[i];
structs[i]++;
strcosts[i] = prices[i][ structs[i] ];
moves.pb(i);
} else {
return click();
}
return turn();
}
ll enh(int i){ // 5-9
if ( enhcosts[i] <= cookie ){
cookie -= enhcosts[i];
enhances[i]++;
enhcosts[i] *= 10;
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;
strcosts[i] = prices[i][ structs[i] ];
structs[i]--;
moves.pb(i+20);
} else {
return click();
}
return turn();
}
ll spend(int i){
return i < 5 ? buy(i) : enh(i - 5);
}
double depturn(int i){
if (i < 5){
double d = strcosts[i];
return d / (base_cps[i] << enhances[i]);
} else if (i < 10){
double d = enhcosts[i-5];
return d / ((base_cps[i-5] << enhances[i-5]) * structs[i-5]);
}
return -1;
}
double sellability(int i){
double selpr = (prices[i][ structs[i] ]+3)/4;
return selpr - (base_cps[i] << enhances[i]) * (10000 - gameturn);
}
bool depr(int i){
double d = depturn(i);
d *= effects[gameturn] != 'S' ? 1 : 0.9;
d *= (10000 - gameturn) / effectrui[gameturn];
return d < (10000 - gameturn);
}
bool operator< (const Game& rhs) const {
return cookie < rhs.cookie;
}
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;
}
}
return ret;
}
void output(const bool sub=false){
char s[114];
REP(i,10000){
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 {
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;
}
};
const string special = "BFS";
void randeffect(){
int v = 0;
int t = prng.rnd() % 200;
effects += 'N' * t;
effects += special[ prng.rnd()%3 ];
v += t + 1;
while( v < 10000){
t = prng.rnd() % 101 + 99;
effects += 'N' * t;
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 + 20;
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();
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.0;
const double startTemp = 5;
double tim = elapsed(st);
int ctr = 0;
const int oneloop = 1000;
while( tim < limittime ){
REP(_,oneloop){
int idx = prng.rnd() % 9000;
if (!g.affordables[idx]) continue;
int bin = __builtin_popcount(g.affordables[idx]);
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 *= 3e-8;
double temper = startTemp * (1.0 - tim / limittime * 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;
}
void test(){
ll v = 0;
REP(i,32){
prng = Xorshift128(i);
effects = "";
randeffect();
v += gameloop().cookie;
}
cerr << v << endl;
}
void exec(){
int v; cin >> v;
cin >> effects;
auto g = gameloop();
g.output(true);
}
int main(){
REP(i,5){
ll pr = base_cost[i];
REP(j,100){
prices[i].pb(pr);
pr = (pr*6 + 4 )/ 5;
}
}
//test();
exec();
}