結果

問題 No.5003 物理好きクリッカー
ユーザー risujirohrisujiroh
提出日時 2018-12-06 18:08:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 318 ms / 10,000 ms
コード長 6,317 bytes
コンパイル時間 2,238 ms
実行使用メモリ 21,984 KB
スコア 62,384,393,659
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 08:57:06
合計ジャッジ時間 15,097 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 314 ms
21,852 KB
testcase_01 AC 316 ms
21,516 KB
testcase_02 AC 312 ms
21,372 KB
testcase_03 AC 316 ms
21,672 KB
testcase_04 AC 316 ms
21,348 KB
testcase_05 AC 313 ms
21,876 KB
testcase_06 AC 313 ms
21,348 KB
testcase_07 AC 315 ms
21,516 KB
testcase_08 AC 313 ms
21,540 KB
testcase_09 AC 312 ms
21,876 KB
testcase_10 AC 315 ms
21,528 KB
testcase_11 AC 316 ms
21,720 KB
testcase_12 AC 314 ms
21,720 KB
testcase_13 AC 315 ms
21,876 KB
testcase_14 AC 315 ms
21,516 KB
testcase_15 AC 314 ms
21,504 KB
testcase_16 AC 314 ms
21,864 KB
testcase_17 AC 315 ms
21,864 KB
testcase_18 AC 318 ms
21,516 KB
testcase_19 AC 318 ms
21,852 KB
testcase_20 AC 311 ms
21,528 KB
testcase_21 AC 315 ms
21,360 KB
testcase_22 AC 314 ms
21,756 KB
testcase_23 AC 314 ms
21,528 KB
testcase_24 AC 312 ms
21,672 KB
testcase_25 AC 314 ms
21,660 KB
testcase_26 AC 312 ms
21,852 KB
testcase_27 AC 314 ms
21,348 KB
testcase_28 AC 314 ms
21,516 KB
testcase_29 AC 311 ms
21,840 KB
testcase_30 AC 312 ms
21,852 KB
testcase_31 AC 313 ms
21,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


// input
constexpr int T = 10'000;
string S;

// outoput
enum struct ActionType { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
struct Action { ActionType type; int id; };
V<Action> actions(T);

// status
lint score;
lint click_power, click_cost;
const V<string> name{"hand", "lily", "factory", "casino", "grimoire"};
V<> cnt(5);
V<lint> power(5), price(5), cost(5);
bool fever, sale;

mt19937 mt(steady_clock::now().time_since_epoch().count());
// [a, b)
int rng(int a, int b) {
  assert(a < b);
  return uniform_int_distribution<>(a, b - 1)(mt);
}
double rng(double a, double b) {
  assert(a < b);
  return uniform_real_distribution<>(a, b)(mt);
}

void read_input() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int _;
  cin >> _;
  assert(_ == T);
  cin >> S;
}

void generate_input() {
  S.assign(T, 'N');
  string bfs = "BFS";
  for (int t = rng(0, 200); t < T; t += rng(100, 201)) {
    S[t] = bfs[rng(0, 3)];
  }
}

void write_output() {
  for (const Action& action : actions) {
    switch(action.type) {
      case ActionType::CLICK:
        cout << "click" << endl;
        break;
      case ActionType::BUY:
        cout << "buy " << name[action.id] << endl;
        break;
      case ActionType::SELL:
        cout << "sell " << name[action.id] << endl;
        break;
      case ActionType::REINFORCE:
        cout << "reinforce " << name[action.id] << endl;
        break;
      case ActionType::ENHCLICK:
        cout << "enhclick " << endl;
        break;
      case ActionType::NOTHING:
        cout << "nothing" << endl;
        break;
    }
    string str;
    cin >> str;
    assert(str == "ok");
  }
}

void init() {
  score = 0;
  click_power = 1, click_cost = 15;
  fill(begin(cnt), end(cnt), 0);
  power = {1, 10, 120, 2'000, 25'000};
  price = {150, 2'000, 30'000, 600'000, 10'000'000};
  for (int id = 0; id < 5; ++id) cost[id] = 10 * price[id];
  fever = sale = false;
}

bool can_buy(int id) {
  if (sale) {
    return score >= (9 * price[id] + 9) / 10;
  } else {
    return score >= price[id];
  }
}

bool can_sell(int id) {
  return cnt[id] > 0;
}

bool can_reinforce(int id) {
  if (sale) {
    return score >= (9 * cost[id] + 9) / 10;
  } else {
    return score >= cost[id];
  }
}

bool can_enhclick() {
  if (sale) {
    return score >= (9 * click_cost + 9) / 10;
  } else {
    return score >= click_cost;
  }
}

void click() {
  score += click_power * (fever ? 7 : 1);
}

void buy(int id) {
  if (sale) {
    score -= (9 * price[id] + 9) / 10;
  } else {
    score -= price[id];
  }
  ++cnt[id];
  price[id] = (6 * price[id] + 4) / 5;
}

void sell(int id) {
  price[id] = price[id] * 5 / 6;
  --cnt[id];
  score += (price[id] + 3) / 4;
}

void reinforce(int id) {
  if (sale) {
    score -= (9 * cost[id] + 9) / 10;
  } else {
    score -= cost[id];
  }
  power[id] <<= 1;
  cost[id] *= 10;
}

void enhclick() {
  if (sale) {
    score -= (9 * click_cost + 9) / 10;
  } else {
    score -= click_cost;
  }
  click_power <<= 1;
  click_cost *= 10;
}

void act(const Action& action) {
  switch(action.type) {
    case ActionType::CLICK:
      click();
      break;
    case ActionType::BUY:
      assert(can_buy(action.id));
      buy(action.id);
      break;
    case ActionType::SELL:
      assert(can_sell(action.id));
      sell(action.id);
      break;
    case ActionType::REINFORCE:
      assert(can_reinforce(action.id));
      reinforce(action.id);
      break;
    case ActionType::ENHCLICK:
      assert(can_enhclick());
      enhclick();
      break;
    case ActionType::NOTHING:
      break;
  }
}

void produce() {
  for (int id = 0; id < 5; ++id) {
    score += power[id] * cnt[id] * (fever ? 7 : 1);
  }
}

void affect(int t) {
  switch(S[t]) {
    case 'B':
      score += (score + 99) / 100;
      break;
    case 'F':
      fever = true;
      break;
    case 'S':
      sale = true;
      break;
  }
  if (t - 20 >= 0 and S[t - 20] == 'F') fever = false;
  if (t - 1 >= 0 and S[t - 1] == 'S') sale = false;
}

lint eval_click() {
  return click_power;
}

lint eval_buy(int id, int t) {
  return power[id] * (T - t) - price[id];
}

lint eval_sell(int id, int t) {
  return (price[id] * 5 / 6 + 3) / 4 - power[id] * (T - t);
}

lint eval_reinforce(int id, int t) {
  return power[id] * cnt[id] * (T - t) - cost[id];
}

lint eval_enhclick(int t) {
  return click_power * (T - t) - click_cost;
}

void solve() {
  for (int t = 0; t < T; ++t) {
    lint best = 0, curr;
    Action best_action = {ActionType::NOTHING, -1};
    // click
    curr = eval_click();
    if (curr > best) {
      best = curr;
      best_action = {ActionType::CLICK, -1};
    }
    // facilities
    for (int id = 0; id < 5; ++id) {
      if (can_buy(id)) {
        curr = eval_buy(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::BUY, id};
        }
      }
      if (can_sell(id)) {
        curr = eval_sell(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::SELL, id};
        }
      }
      if (can_reinforce(id)) {
        curr = eval_reinforce(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::REINFORCE, id};
        }
      }
    }
    // enhclick
    if (can_enhclick()) {
      curr = eval_enhclick(t);
      if (curr > best) {
        best = curr;
        best_action = {ActionType::ENHCLICK, -1};
      }
    }
    act(actions[t] = best_action);
    produce();
    affect(t);
  }
}

int main(int argc, char* argv[]) {
  if (argc == 1) {
    read_input();
    init();
    solve();
    write_output();
  } else {
    assert(argc == 2);
    lint total_score = 0;
    for (int _ = 0; _ < stoi(argv[1]); ++_) {
      generate_input();
      init();
      solve();
      total_score += score;
    }
    cerr << "Score: " << total_score << endl;
  }
}
0