結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 iehn_
|
| 提出日時 | 2018-12-09 23:05:13 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,509 bytes |
| コンパイル時間 | 1,413 ms |
| 実行使用メモリ | 126,844 KB |
| スコア | 0 |
| 平均クエリ数 | 1.00 |
| 最終ジャッジ日時 | 2021-07-19 09:17:06 |
| 合計ジャッジ時間 | 27,939 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / 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 State&)’: main.cpp:158:1: warning: no return statement in function returning non-void [-Wreturn-type] } ^
ソースコード
// 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};
struct State{
long c;
long pro;
long pcc;
int bi;
int cmd;
int cmds[160];
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;
}
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){
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) + 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){
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 << "}]";
}
char S[N];
int R[N];
const int QM = 55000;
const int QMC = QM / 11 - 110;
State Q[3][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(){
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][0] = State();
int nqs = 1;
int cqs = 0;
int bqs = 0;
for(int t=0; t<N; t++){
auto &nq = Q[(t+1) % 3];
auto &cq = Q[t % 3];
auto &bq = Q[(t+2) % 3];
bqs = cqs;
cqs = nqs;
nqs = 0;
sort(&cq[0], &cq[cqs]);
int tc = 0;
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 mc = 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(mp < qi.pro || (mp == qi.pro && mc < qi.pcc)){
qc++;
mp = qi.pro;
mc = qi.pcc;
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) break;
}
}
sf = 0;
if(S[t] == 'F'){
ft = t + 20;
}else if(S[t] == 'S'){
sf = 1;
}
}
int lqs = nqs;
sort(&Q[1][0], &Q[1][lqs]);
int ni = lqs - 1;
for(int i=0; i<N; i++){
R[i] = CLICK;
}
const auto& bs = Q[0][Q[1][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[0][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);
double mainstart = GetSeconds();
cerr << setprecision(10);
init();
cerr << "init_time: " << GetSeconds() - mainstart << endl;
solve();
output();
cerr << "main_time: " << GetSeconds() - mainstart << endl;
return 0;
}