結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 iehn_
|
| 提出日時 | 2018-12-08 16:41:04 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,807 bytes |
| コンパイル時間 | 1,698 ms |
| 実行使用メモリ | 21,984 KB |
| スコア | 0 |
| 平均クエリ数 | 1.00 |
| 最終ジャッジ日時 | 2021-07-19 09:11:17 |
| 合計ジャッジ時間 | 24,739 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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:170: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:174: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];
struct Product{
long pro;
int bc[FM];
int 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 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;
}
vector<State> nextStates(bool bf, bool sf, bool ff, int qi){
vector<State> vs;
State s = State(c, p, qi, CLICK);
if(ff){
s.c += s.p.pro * 7;
}else{
s.c += s.p.pro;
}
vs.push_back(s);
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){
State sa = State(c-ac, p, qi, REF+i);
sa.p.ac[i]++;
sa.p.calc_pro();
if(bf) sa.c += sa.c / 100;
if(ff){
sa.c += (sa.p.pro - pow(2, sa.p.ac[0])) * 7;
}else{
sa.c += sa.p.pro - pow(2, sa.p.ac[0]);
}
vs.push_back(sa);
}
}
if(i==0) continue;
if(p.bc[i] <= (p.ac[i]+1) * 10){
long bc = bcosts[i][p.bc[i]];
if(sf) bc -= bc / 10;
else if(c - p.pro >= bc) continue;
if(c >= bc){
State sb = State(c-bc, p, qi, BUY+i);
sb.p.bc[i]++;
sb.p.calc_pro();
if(bf) sb.c += sb.c / 100;
if(ff){
sb.c += (sb.p.pro - pow(2, sb.p.ac[0])) * 7;
}else{
sb.c += sb.p.pro - pow(2, sb.p.ac[0]);
}
vs.push_back(sb);
}
}
}
return vs;
}
};
ostream& operator<<(ostream& os, const Product& p){
os << "P{" << p.pro;
for(int i=0; i<FM; i++){
os << " (" << p.bc[i] << ", " << 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];
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;
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();
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 : Q[t][cqs-1].nextStates(bf,sf,ff,cqs-1)){
nq.push_back(s);
}
Product mp = Q[t][cqs-1].p;
if(t % 1000 == 999){
cerr << t << ": " << cqs << ", " << Q[t][cqs-1] << endl;
}
int qc = 1;
for(int i=cqs-2; i>=0; i--){
auto qi = Q[t][i];
if(mp < qi.p){
qc++;
mp = qi.p;
for(const auto &s : qi.nextStates(bf,sf,ff,i)){
nq.push_back(s);
}
if(qc > 3999) 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;
R[i-1] = Q[i][ni].cmd;
ni = Q[i][ni].bi;
}
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;
}