結果

問題 No.5003 物理好きクリッカー
ユーザー iehn_iehn_
提出日時 2018-12-13 17:41:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 5,476 ms / 10,000 ms
コード長 7,619 bytes
コンパイル時間 1,506 ms
実行使用メモリ 452,736 KB
スコア 306,019,180,759
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 09:30:23
合計ジャッジ時間 165,637 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,681 ms
452,640 KB
testcase_01 AC 5,327 ms
452,588 KB
testcase_02 AC 4,732 ms
452,580 KB
testcase_03 AC 4,552 ms
452,148 KB
testcase_04 AC 4,971 ms
452,468 KB
testcase_05 AC 4,610 ms
452,484 KB
testcase_06 AC 4,980 ms
452,144 KB
testcase_07 AC 4,467 ms
452,648 KB
testcase_08 AC 5,299 ms
452,680 KB
testcase_09 AC 4,412 ms
452,424 KB
testcase_10 AC 5,428 ms
452,324 KB
testcase_11 AC 4,528 ms
452,636 KB
testcase_12 AC 5,476 ms
452,372 KB
testcase_13 AC 4,717 ms
452,256 KB
testcase_14 AC 4,593 ms
452,392 KB
testcase_15 AC 5,016 ms
452,228 KB
testcase_16 AC 4,563 ms
452,600 KB
testcase_17 AC 4,583 ms
452,368 KB
testcase_18 AC 4,598 ms
452,540 KB
testcase_19 AC 4,468 ms
452,576 KB
testcase_20 AC 4,983 ms
452,424 KB
testcase_21 AC 4,496 ms
452,148 KB
testcase_22 AC 4,550 ms
452,220 KB
testcase_23 AC 4,946 ms
452,352 KB
testcase_24 AC 5,325 ms
452,384 KB
testcase_25 AC 4,931 ms
452,272 KB
testcase_26 AC 4,732 ms
452,412 KB
testcase_27 AC 5,050 ms
452,388 KB
testcase_28 AC 5,001 ms
452,580 KB
testcase_29 AC 4,487 ms
452,488 KB
testcase_30 AC 4,543 ms
452,644 KB
testcase_31 AC 5,232 ms
452,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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 = 8.3;
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 = 192;

struct State{
  long c;
  long pro;
  long pcc;
  long bbc;
  int bi;
  int cmd;
  int cmds[CM];

  State(){ c = bi = cmd = pcc = bbc = 0; pro = 1; cmds[0] = 0; }

  void copy(long _c, long _pro, long _pcc, long _bbc, int _bi, int _cmd){
    c = _c;
    pro = _pro;
    pcc = _pcc;
    bbc = _bbc;
    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, bbc, 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((pcc >> asft[i] & 7) < 7){
        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, bbc, 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) < 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, bbc + bc, 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) << ", bc: " << s.bbc << ", 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 = 110000;
const int QMC = QM / 11 - 110;
const int QIM = 5;
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, 2) + N;
  }
  long etc = 0;
  for(int t=0; t<N; t++){
    etc += pow(N-t, 2) + N;
    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-1)){
        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;
}
0