結果

問題 No.5003 物理好きクリッカー
ユーザー iehn_iehn_
提出日時 2018-12-09 17:35:32
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 6,881 bytes
コンパイル時間 1,713 ms
実行使用メモリ 992,512 KB
スコア 225,375,685,236
平均クエリ数 9375.00
最終ジャッジ日時 2021-07-19 09:14:53
合計ジャッジ時間 59,829 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge10
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,694 ms
448,372 KB
testcase_01 AC 1,399 ms
371,492 KB
testcase_02 AC 1,744 ms
480,492 KB
testcase_03 AC 1,788 ms
491,068 KB
testcase_04 AC 1,367 ms
342,912 KB
testcase_05 AC 1,469 ms
378,824 KB
testcase_06 AC 1,475 ms
393,200 KB
testcase_07 AC 1,877 ms
506,572 KB
testcase_08 AC 1,862 ms
503,816 KB
testcase_09 AC 1,619 ms
434,696 KB
testcase_10 AC 1,653 ms
441,276 KB
testcase_11 AC 1,525 ms
416,936 KB
testcase_12 MLE -
testcase_13 AC 1,562 ms
413,744 KB
testcase_14 AC 1,356 ms
351,164 KB
testcase_15 AC 1,518 ms
397,368 KB
testcase_16 AC 1,308 ms
336,672 KB
testcase_17 AC 1,353 ms
346,748 KB
testcase_18 AC 1,724 ms
475,360 KB
testcase_19 AC 1,556 ms
419,736 KB
testcase_20 AC 1,694 ms
455,512 KB
testcase_21 AC 1,754 ms
487,228 KB
testcase_22 MLE -
testcase_23 MLE -
testcase_24 AC 1,466 ms
379,680 KB
testcase_25 AC 1,433 ms
367,520 KB
testcase_26 AC 1,680 ms
447,544 KB
testcase_27 AC 1,570 ms
407,568 KB
testcase_28 AC 1,712 ms
456,908 KB
testcase_29 AC 1,812 ms
492,776 KB
testcase_30 MLE -
testcase_31 AC 1,683 ms
992,512 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 = 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] = {0, 3, 12, 21, 30, 39};

long calc_pro_pcc(long pcc){
  long 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);
  }
  return pro;
}

vector<tuple<long, long, long, int>> next_states(tuple<long, long, long, int> tp, bool bf, bool sf, bool ff, int qi){
  long c = get<0>(tp);
  long pro = get<1>(tp);
  long pcc = get<2>(tp);
  int qi5 = qi << 5;
  vector<tuple<long, long, long, int>> vs;
  long sc = c;
  if(bf) sc += sc / 100;
  if(ff){
    sc += pro * 7;
  }else{
    sc += pro;
  }
  vs.emplace_back(sc, pro, pcc, qi5 | CLICK);
  for(int i=0; i<FM; i++){
    if((i<FM-1 || (pcc >> asft[i] & 7) <= (pcc >> asft[i+1] & 7)) && (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){
        long sac = c - ac;
        long sapcc = pcc;
        sapcc += apls[i];
        long sapro = calc_pro_pcc(sapcc);
        if(bf) sac += sac / 100;
        if(ff){
          sac += (sapro - pow(2, sapcc & 7)) * 7;
        }else{
          sac += sapro - pow(2, sapcc & 7);
        }
        vs.emplace_back(sac, sapro, sapcc, qi5 | REF+i);
      }
    }
    if(i==0) continue;
    if((pcc >> bsft[i] & 63) <= ((pcc >> asft[i] & 7) + 1) * 10 && (pcc >> bsft[i] & 63) < 63){
      long bc = bcosts[i][(pcc >> bsft[i] & 63)];
      if(sf) bc -= bc / 10;
      else if(c - pro >= bc) continue;
      if(c >= bc){
        long sbc = c - bc;
        long sbpcc = pcc;
        sbpcc += bpls[i];
        long sbpro = calc_pro_pcc(sbpcc);
        if(bf) sbc += sbc / 100;
        if(ff){
          sbc += (sbpro - pow(2, sbpcc & 7)) * 7;
        }else{
          sbc += sbpro - pow(2, sbpcc & 7);
        }
        vs.emplace_back(sbc, sbpro, sbpcc, qi5 | BUY+i);
      }
    }
  }
  return vs;
}

string tpstr(tuple<long, long, long, int> tp){
  long sc = get<0>(tp);
  long spro = get<1>(tp);
  long spcc = get<2>(tp);
  int sbicmd = get<3>(tp);
  ostringstream os;
  os << "S[" << sc << ", " << log(sc) / log(10) << ", bi: " << (sbicmd >> 5) << ", cmd: " << (sbicmd & 31) << ", ";
  os << "P{" << spro;
  for(int i=0; i<FM; i++){
    os << " (" << (spcc >> bsft[i] & 63) << ", " << (spcc >> asft[i] & 7) << ")";
  }
  os << "}]";
  return os.str();
}

char S[N];
int R[N];
vector<tuple<long, long, long, int>> Q[N+1];
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(){
  long c = 0;
  int bcount[FM] = {1, 0, 0, 0, 0, 0};
  int acount[FM] = {0, 0, 0, 0, 0, 0};
  bool sf = 0;
  int ft = -1;
  Q[0].emplace_back(0, 1, 0, 0);
  for(int t=0; t<N; t++){
    auto &nq = Q[t+1];
    int cqs = Q[t].size();
    sort(&Q[t][0], &Q[t][cqs]);
    int tc = 0;
    bool ff = ft >= t;
    bool bf = S[t] == 'B';
    for(const auto &s : next_states(Q[t][cqs-1], bf,sf,ff,cqs-1)){
      nq.push_back(s);
    }
    long mp = get<1>(Q[t][cqs-1]);
    long mc = get<2>(Q[t][cqs-1]);
    if(t % 1000 == 999){
      cerr << t << ": " << cqs << ", " << tpstr(Q[t][cqs-1]) << endl;
    }
    int qc = 1;
    for(int i=cqs-2; i>=0; i--){
      auto qi = Q[t][i];
      long qipro = get<1>(qi);
      long qipcc = get<2>(qi);
      if(mp < qipro || (mp == qipro && mc < qipcc)){
        qc++;
        mp = qipro;
        mc = qipcc;
        for(const auto &s : next_states(qi, bf,sf,ff,i)){
          nq.push_back(s);
        }
        if(qc > 2499) break;
      }
    }
    sf = 0;
    if(S[t] == 'F'){
      ft = t + 20;
    }else if(S[t] == 'S'){
      sf = 1;
    }
  }
  int lqs = Q[N].size();
  sort(&Q[N][0], &Q[N][lqs]);
  int ni = lqs - 1;
  for(int i=N; i>0; i--){
    // if(Q[i][ni].cmd != CLICK) cerr << i << ":: " << Q[i][ni] << endl;
    int bicmd = get<3>(Q[i][ni]);
    R[i-1] = bicmd & 31;
    ni = bicmd >> 5;
  }
}

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);
  double mainstart = GetSeconds();
  cerr << setprecision(10);
  init();
  cerr << "init_time: " << GetSeconds() - mainstart << endl;
  solve();
  output();
  cerr << "main_time: " << GetSeconds() - mainstart << endl;
  return 0;
}
0