#302677 (C++11) No.5003 物理好きクリッカー

提出ソース

結果

問題	No.5003 物理好きクリッカー
ユーザー	iehn_
提出日時	2018-12-08 22:00:45
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	8,609 bytes
コンパイル時間	1,648 ms
実行使用メモリ	21,984 KB
スコア	0
平均クエリ数	1.00
最終ジャッジ日時	2021-07-19 09:12:06
合計ジャッジ時間	25,366 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘std::ostream& operator<<(std::ostream&, const Product&)’:
main.cpp:187:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
main.cpp: In function ‘std::ostream& operator<<(std::ostream&, const State&)’:
main.cpp:191:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

raw source code

// 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];

struct Product{
  long pro;
  unsigned char bc[FM];
  unsigned char ac[FM];

  Product(){
    pro = 1;
    for(int i=0; i<FM; i++){
      bc[i] = 0;
      ac[i] = 0;
    }
    bc[0] = 1;
  }
  Product(const Product& p){
    pro = p.pro;
    for(int i=0; i<FM; i++){
      bc[i] = p.bc[i];
      ac[i] = p.ac[i];
    }
  }

  bool operator<(const Product &a) const{
    if(pro != a.pro) return pro < a.pro;
    for(int i=FM-1; i>0; i--){
      if(ac[i] != a.ac[i]) return ac[i] < a.ac[i];
      if(bc[i] != a.bc[i]) return bc[i] < a.bc[i];
    }
    return ac[0] < a.ac[0];
  }

  void copy(const Product &_p){
    pro = _p.pro;
    for(int i=0; i<FM; i++){
      bc[i] = _p.bc[i];
      ac[i] = _p.ac[i];
    }
  }

  void calc_pro(){
    pro = pow(2, ac[0]);
    for(int i=1; i<FM; i++){
      pro += FP[i] * bc[i] * pow(2, ac[i]);
    }
  }
};

struct State{
  long c;
  Product p;
  int bi;
  int cmd;

  State(){ c = bi = cmd = 0; }
  State(long _c, const Product& _p, int _bi, int _cmd){
    c = _c;
    p = Product(_p);
    bi = _bi;
    cmd = _cmd;
  }

  bool operator<(const State &a) const{
    return c != a.c ? c < a.c : p < a.p;
  }

  void copy(long _c, const Product &_p, int _bi, int _cmd){
    c = _c;
    p.copy(_p);
    bi = _bi;
    cmd = _cmd;
  }

  int nextStates(bool bf, bool sf, bool ff, int qi, State *sts, int sti){
    sts[sti].copy(c, p, qi, CLICK);
    if(ff){
      sts[sti].c += sts[sti].p.pro * 7;
    }else{
      sts[sti].c += sts[sti].p.pro;
    }
    int si = sti + 1;
    for(int i=0; i<FM; i++){
      if(i<FM-1 || p.ac[i] <= p.ac[i+1]){
        long ac = acosts[i][p.ac[i]];
        if(sf) ac -= ac / 10;
        else if(c - p.pro >= ac) continue;
        if(c >= ac
            && (p.ac[i] < (p.bc[i]+5) / 10 || (i == 0 && p.ac[i] < 4))
            && (i == FM-1 || p.ac[i] >= p.ac[i+1] - 1)){
          sts[si].copy(c-ac, p, qi, REF+i);
          sts[si].p.ac[i]++;
          sts[si].p.calc_pro();
          if(bf) sts[si].c += sts[si].c / 100;
          if(ff){
            sts[si].c += (sts[si].p.pro - pow(2, sts[si].p.ac[0])) * 7;
          }else{
            sts[si].c += sts[si].p.pro - pow(2, sts[si].p.ac[0]);
          }
          si++;
        }
      }
      if(i==0) continue;
      if(p.bc[i] <= p.ac[i] * 10 + 7
          && (i == FM-1 || p.bc[i] >= p.bc[i+1])){
        long bc = bcosts[i][p.bc[i]];
        if(sf) bc -= bc / 10;
        else if(c - p.pro >= bc) continue;
        if(c >= bc){
          sts[si].copy(c-bc, p, qi, BUY+i);
          sts[si].p.bc[i]++;
          sts[si].p.calc_pro();
          if(bf) sts[si].c += sts[si].c / 100;
          if(ff){
            sts[si].c += (sts[si].p.pro - pow(2, sts[si].p.ac[0])) * 7;
          }else{
            sts[si].c += sts[si].p.pro - pow(2, sts[si].p.ac[0]);
          }
          si++;
        }
      }
    }
    return si - sti;
  }
};

ostream& operator<<(ostream& os, const Product& p){
  os << "P{" << p.pro;
  for(int i=0; i<FM; i++){
    os << " (" << (int)p.bc[i] << ", " << (int)p.ac[i] << ")";
  }
  os << "}";
}

ostream& operator<<(ostream& os, const State& s){
  os << "S[" << s.c << ", " << log(s.c) / log(10) << ", bi: " << s.bi << ", cmd: " << s.cmd << ", " << s.p << "]";
}


char S[N];
int R[N];
const int TSM = 10000;
State TS[TSM];
vector<State> 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;
  bool sf = 0;
  int ft = -1;
  Q[0].emplace_back();
  int sti = 1;
  for(int t=0; t<N; t++){
    sort(&TS[0], &TS[sti]);
    int tc = 0;
    bool ff = ft >= t;
    bool bf = S[t] == 'B';

    Product tmp = TS[sti-1].p;
    int tqc = 1;
    auto &tq = Q[t];
    tq.push_back(TS[sti-1]);
    for(int i=sti-2; i>=0; i--){
      auto qi = TS[i];
      if(tmp < qi.p){
        tqc++;
        tmp = qi.p;
        tq.push_back(qi);
        if(tqc > 3999) break;
      }
    }
    int cqs = Q[t].size();

    sti = 0;
    sti += Q[t][0].nextStates(bf,sf,ff,0, TS, sti);
    Product mp = Q[t][0].p;
    int qc = 1;
    if(t % 1000 == 999){
      cerr << t << ": " << cqs << ", " << Q[t][0] << endl;
    }
    for(int i=1; i<cqs; i++){
      auto qi = Q[t][i];
      qc++;
      sti += qi.nextStates(bf,sf,ff,i, TS, sti);
      if(sti > TSM - 50) break;
    }
    sf = 0;
    if(S[t] == 'F'){
      ft = t + 20;
    }else if(S[t] == 'S'){
      sf = 1;
    }
  }
  sort(&TS[0], &TS[sti]);
  Q[N].push_back(TS[sti-1]);
  int ni = 0;
  int qsz = 0;
  for(int i=N; i>0; i--){
    // if(Q[i][ni].cmd != CLICK) cerr << i << ":: " << Q[i][ni] << endl;
    R[i-1] = Q[i][ni].cmd;
    ni = Q[i][ni].bi;
    qsz += Q[i].size();
  }
  cerr << "qsz: " << qsz << endl;

  int bcount[FM] = {1, 0, 0, 0, 0, 0};
  int acount[FM] = {0, 0, 0, 0, 0, 0};
  for(int t=0; t<N; t++){
    int tr = R[t];
    for(int i=FM-1; i>=0; i--){
      long ac = acosts[i][acount[i]];
      long bc = bcosts[i][bcount[i]];
      if(sf){
        ac -= ac / 10;
        bc -= bc / 10;
      }
      if(ac <= c && tr == REF + i){
        c -= ac;
        acount[i]++;
        break;
      }
      if(i > 0 && bc <= c && tr == BUY + i){
        c -= bc;
        bcount[i]++;
        break;
      }
    }
    R[t] = tr;
    long cc = 0;
    if(tr == CLICK){
      cc = bcount[0] * pow(2, acount[0]);
    }
    for(int i=1; i<FM; i++){
      if(bcount[i] < 1) continue;
      cc += bcount[i] * pow(2, acount[i]) * FP[i];
    }
    if(ft >= t){
      cc *= 7;
    }
    // if(t % 1000 == 999) cerr << t << ": " << c << ", cc: " << cc << endl;
    sf = 0;
    if(S[t] == 'N'){
    }else if(S[t] == 'B'){
      c += c / 100 + (c%100 ? 1 : 0);
    }else if(S[t] == 'F'){
      ft = t + 20;
    }else if(S[t] == 'S'){
      sf = 1;
    }
    c += cc;
  }
  for(int i=0; i<FM; i++){
    cerr << "i: " << i << " bc: " << bcount[i] << " ac: " << acount[i] << endl;
  }
  cerr << "c: " << c << " log: " << log(c) / log(10) << endl;
}

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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード