結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 iehn_
|
| 提出日時 | 2018-12-13 15:46:14 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,860 bytes |
| コンパイル時間 | 2,193 ms |
| 実行使用メモリ | 792,364 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2021-07-19 09:26:40 |
| 合計ジャッジ時間 | 34,597 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | MLE | - |
| 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 | -- | - |
ソースコード
// C++11
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <bitset>
using namespace std;
inline long long GetTSC() {
long long lo, hi;
asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
return lo + (hi << 32);
}
inline double GetSeconds() {
return GetTSC() / 2.8e9;
}
struct XorShift {
uint64_t x = 88172645463325252ULL;
XorShift() {}
void setSeed(uint64_t seed) { x = seed; }
uint64_t next() { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; }
int nextInt(int n) {
uint64_t upper = 0xFFFFFFFFFFFFFFFFULL / n * n;
uint64_t v = next();
while (v >= upper) { v = next(); }
return v % n;
}
double nextDouble() {
uint64_t v = next() >> 11; // 53bit
return (double)v / (1ULL << 53);
}
};
const double TO = 9.9;
const double eps = 1e-7;
const double inf = 1e7;
const int N = 10000;
const int CLICK = 1;
const int FM = 6;
const string FS[FM] = {"enhclick", "hand", "lily", "factory", "casino", "grimoire"};
const int FP[FM] = {1, 1, 10, 120, 2000, 25000};
const int FB[FM] = {-1, 150, (int)2e3, (int)3e4, (int)6e5, (int)1e7};
const int FA[FM] = {15, 1500, (int)2e4, (int)3e5, (int)6e6, (int)1e8};
const int BUY = 2;
const int SELL = BUY + FM;
const int REF = BUY + FM * 2;
long bcosts[FM][256];
long acosts[FM][16];
const long amsk[FM] = {7, 7l<<9, 7l<<18, 7l<<27, 7l<<36, 7l<<45};
const long apls[FM] = {1, 1l<<9, 1l<<18, 1l<<27, 1l<<36, 1l<<45};
const int asft[FM] = {0, 9, 18, 27, 36, 45};
const long bmsk[FM] = {0, 63l<<3, 63l<<12, 63l<<21, 63l<<30, 63l<<39};
const long bpls[FM] = {0, 1l<<3, 1l<<12, 1l<<21, 1l<<30, 1l<<39};
const int bsft[FM] = {63, 3, 12, 21, 30, 39};
const int CM = 160;
struct State{
long c;
long pro;
long pcc;
int bi;
int cmd;
int cmds[CM];
State(){ c = bi = cmd = pcc = 0; pro = 1; cmds[0] = 0; }
State(long _c, long _pro, long _pcc, int _bi, int _cmd){
c = _c;
pro = _pro;
pcc = _pcc;
bi = _bi;
cmd = _cmd;
}
void copy(long _c, long _pro, long _pcc, int _bi, int _cmd){
c = _c;
pro = _pro;
pcc = _pcc;
bi = _bi;
cmd = _cmd;
}
bool operator<(const State &a) const{
return c != a.c ? c < a.c : pro != a.pro ? pro < a.pro : pcc < a.pcc;
}
void calc_pro(){
pro = pow(2, pcc & 7);
for(int i=1; i<FM; i++){
pro += FP[i] * (pcc >> bsft[i] & 63) * pow(2, pcc >> asft[i] & 7);
}
}
int nextStates(bool bf, bool sf, bool ff, int qi, State vs[], int nqs){
State &s = vs[nqs++];
s.copy(c, pro, pcc, qi, CLICK);
if(bf) s.c += s.c / 100;
if(ff){
s.c += s.pro * 7;
}else{
s.c += s.pro;
}
if(cmds[0] > CM - 5) return nqs;
for(int i=0; i<FM; i++){
if((i<FM-1 || (pcc >> asft[i] & 7) <= (pcc >> asft[i+1] & 7)) && (pcc >> asft[i] & 7) < 5){
long ac = acosts[i][pcc >> asft[i] & 7];
if(sf) ac -= ac / 10;
else if(c - pro >= ac) continue;
if(c >= ac){
State &sa = vs[nqs++];
sa.copy(c-ac, pro, pcc, qi, REF+i);
sa.pcc += apls[i];
sa.calc_pro();
if(bf) sa.c += sa.c / 100;
if(ff){
sa.c += (sa.pro - pow(2, sa.pcc & 7)) * 7;
}else{
sa.c += sa.pro - pow(2, sa.pcc & 7);
}
}
}
if(i==0) continue;
if((pcc >> bsft[i] & 63) <= (pcc >> asft[i] & 7) * 10 + 5 && (pcc >> bsft[i] & 63) < 48){
long bc = bcosts[i][(pcc >> bsft[i] & 63)];
if(sf) bc -= bc / 10;
else if(c - pro >= bc) continue;
if(c >= bc){
State &sb = vs[nqs++];
sb.copy(c-bc, pro, pcc, qi, BUY+i);
sb.pcc += bpls[i];
sb.calc_pro();
if(bf) sb.c += sb.c / 100;
if(ff){
sb.c += (sb.pro - pow(2, sb.pcc & 7)) * 7;
}else{
sb.c += sb.pro - pow(2, sb.pcc & 7);
}
}
}
}
return nqs;
}
};
ostream& operator<<(ostream& os, const State& s){
os << "S[" << s.c << ", " << log(s.c) / log(10) << ", bi: " << s.bi << ", cmd: " << s.cmd << ", ";
os << "P{" << s.pro;
for(int i=0; i<FM; i++){
os << " (" << (s.pcc >> bsft[i] & 63) << ", " << (s.pcc >> asft[i] & 7) << ")";
}
os << "}]";
return os;
}
char S[N];
int R[N];
const int QM = 88000;
const int QMC = QM / 11 - 110;
const int QIM = 13;
State Q[QIM][QM];
double starttime, gt;
int tt,ctt;
XorShift xs;
void init(){
int n;
scanf("%d%s", &n, S);
for(int i=0; i<FM; i++){
acosts[i][0] = FA[i];
for(int j=1; j<16; j++){
acosts[i][j] = acosts[i][j-1] * 10;
}
if(i == 0) continue;
bcosts[i][0] = FB[i];
for(int j=1; j<256; j++){
long bb = bcosts[i][j-1];
bcosts[i][j] = bb + bb / 5 + (bb % 5 ? 1 : 0);
}
}
}
long calc_score(){
long r = 0;
return r;
}
void solve(){
bool sf = 0;
int ft = -1;
Q[0][0] = State();
int nqs = 1;
int cqs = 0;
long etm = 0;
for(int i=0; i<N; i++){
etm += pow(N-i, 3);
}
long etc = 0;
for(int t=0; t<N; t++){
etc += pow(N-t, 3);
double et = TO + starttime - TO * 0.9 * (etm-etc) / etm;
auto &nq = Q[(t+1) % QIM];
auto &cq = Q[t % QIM];
auto &bq = Q[(t-1) % QIM];
cqs = nqs;
nqs = 0;
sort(&cq[0], &cq[cqs]);
bool ff = ft >= t;
bool bf = S[t] == 'B';
nqs = cq[cqs-1].nextStates(bf,sf,ff,cqs-1,nq,nqs);
if(t > 0){
int i = cqs-1;
const auto &bs = bq[cq[i].bi].cmds;
memcpy(cq[i].cmds, bs, (bs[0]+1) * sizeof(bs[0]));
if(cq[i].cmd != CLICK){
cq[i].cmds[++cq[i].cmds[0]] = (t-1) << 5 | cq[i].cmd;
}
}
long mp = cq[cqs-1].pro;
long mx = cq[cqs-1].c + mp * 500;
set<long> pccs;
pccs.clear();
pccs.insert(cq[cqs-1].pcc);
if(t % 1000 == 999){
cerr << t << ": " << cqs << ", " << cq[cqs-1] << endl;
}
int qc = 1;
for(int i=cqs-2; i>=0; i--){
auto qi = cq[i];
if(mx <= qi.c + qi.pro * (N-t)){
if(pccs.find(qi.pcc) != pccs.end()) continue;
pccs.insert(qi.pcc);
qc++;
mx = qi.c + qi.pro * (N-t);
nqs = qi.nextStates(bf,sf,ff,i,nq,nqs);
const auto &bs = bq[cq[i].bi].cmds;
memcpy(cq[i].cmds, bs, (bs[0]+1) * sizeof(bs[0]));
if(cq[i].cmd != CLICK){
cq[i].cmds[++cq[i].cmds[0]] = (t-1) << 5 | cq[i].cmd;
}
if(qc > QMC || GetSeconds() >= et) break;
}
}
sf = 0;
if(S[t] == 'F'){
ft = t + 20;
}else if(S[t] == 'S'){
sf = 1;
}
}
int lqs = nqs;
sort(&Q[N % QIM][0], &Q[N % QIM][lqs]);
int ni = lqs - 1;
for(int i=0; i<N; i++){
R[i] = CLICK;
}
const auto& bs = Q[(N-1) % QIM][Q[N % QIM][ni].bi].cmds;
for(int j=1; j<=bs[0]; j++){
int tn = bs[j] >> 5;
R[tn] = bs[j] & 31;
}
R[N-1] = Q[N % QIM][ni].cmd;
}
void output(){
int t = 0;
string s;
for(int i=0; i<N; i++){
int ri = R[i];
if(ri == CLICK){
cout << "click" << endl;
}else if(ri == REF){
cout << "enhclick" << endl;
}else if(ri >= BUY && ri < BUY + FM){
cout << "buy " << FS[ri - BUY] << endl;
}else if(ri >= REF && ri < REF + FM){
cout << "reinforce " << FS[ri - REF] << endl;
}else if(ri >= SELL && ri < SELL + FM){
cout << "sell " << FS[ri - SELL] << endl;
}
cin >> s;
if(i == 0) cerr << "s: " << s << endl;
if(s == "-1") return;
if(s[0] == '-'){
cerr << 1 / t << endl;
}
}
}
int main() {
srand((unsigned) time(NULL));
xs.setSeed(rand() % 65536 || 65537);
starttime = GetSeconds();
double mainstart = GetSeconds();
cerr << setprecision(10);
init();
cerr << "init_time: " << GetSeconds() - mainstart << endl;
solve();
output();
cerr << "main_time: " << GetSeconds() - mainstart << endl;
return 0;
}