結果
問題 | No.5017 Tool-assisted Shooting |
ユーザー | takumi152 |
提出日時 | 2023-07-16 16:17:54 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 9,280 bytes |
コンパイル時間 | 4,464 ms |
コンパイル使用メモリ | 283,020 KB |
実行使用メモリ | 24,516 KB |
スコア | 17,858 |
平均クエリ数 | 117.56 |
最終ジャッジ日時 | 2023-07-16 16:20:55 |
合計ジャッジ時間 | 171,695 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 406 ms
23,904 KB |
testcase_01 | TLE | - |
testcase_02 | AC | 582 ms
23,376 KB |
testcase_03 | AC | 804 ms
24,288 KB |
testcase_04 | AC | 398 ms
24,060 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 1,996 ms
24,504 KB |
testcase_08 | AC | 353 ms
23,556 KB |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | AC | 233 ms
24,024 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 775 ms
23,376 KB |
testcase_16 | AC | 486 ms
23,292 KB |
testcase_17 | TLE | - |
testcase_18 | AC | 636 ms
24,156 KB |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | AC | 464 ms
23,280 KB |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | AC | 388 ms
24,168 KB |
testcase_26 | TLE | - |
testcase_27 | AC | 385 ms
24,168 KB |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | AC | 633 ms
24,396 KB |
testcase_32 | TLE | - |
testcase_33 | AC | 459 ms
23,280 KB |
testcase_34 | AC | 589 ms
23,316 KB |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | AC | 362 ms
24,024 KB |
testcase_38 | TLE | - |
testcase_39 | AC | 1,313 ms
23,844 KB |
testcase_40 | TLE | - |
testcase_41 | TLE | - |
testcase_42 | AC | 527 ms
24,396 KB |
testcase_43 | AC | 1,230 ms
23,388 KB |
testcase_44 | TLE | - |
testcase_45 | AC | 792 ms
23,568 KB |
testcase_46 | AC | 654 ms
24,264 KB |
testcase_47 | TLE | - |
testcase_48 | TLE | - |
testcase_49 | AC | 622 ms
23,292 KB |
testcase_50 | AC | 534 ms
24,060 KB |
testcase_51 | AC | 322 ms
23,844 KB |
testcase_52 | AC | 552 ms
23,556 KB |
testcase_53 | AC | 1,489 ms
23,556 KB |
testcase_54 | TLE | - |
testcase_55 | AC | 773 ms
24,036 KB |
testcase_56 | AC | 563 ms
23,412 KB |
testcase_57 | AC | 528 ms
24,036 KB |
testcase_58 | AC | 721 ms
23,736 KB |
testcase_59 | AC | 519 ms
24,288 KB |
testcase_60 | TLE | - |
testcase_61 | AC | 1,528 ms
23,844 KB |
testcase_62 | AC | 345 ms
24,144 KB |
testcase_63 | TLE | - |
testcase_64 | AC | 711 ms
23,748 KB |
testcase_65 | TLE | - |
testcase_66 | TLE | - |
testcase_67 | AC | 473 ms
24,336 KB |
testcase_68 | TLE | - |
testcase_69 | AC | 671 ms
23,412 KB |
testcase_70 | AC | 735 ms
23,376 KB |
testcase_71 | AC | 571 ms
24,264 KB |
testcase_72 | TLE | - |
testcase_73 | AC | 221 ms
24,168 KB |
testcase_74 | TLE | - |
testcase_75 | AC | 506 ms
23,448 KB |
testcase_76 | AC | 429 ms
23,280 KB |
testcase_77 | AC | 571 ms
24,324 KB |
testcase_78 | TLE | - |
testcase_79 | AC | 1,032 ms
24,264 KB |
testcase_80 | AC | 438 ms
24,516 KB |
testcase_81 | TLE | - |
testcase_82 | AC | 319 ms
24,216 KB |
testcase_83 | AC | 718 ms
24,240 KB |
testcase_84 | AC | 442 ms
23,532 KB |
testcase_85 | TLE | - |
testcase_86 | AC | 389 ms
24,288 KB |
testcase_87 | TLE | - |
testcase_88 | AC | 577 ms
24,336 KB |
testcase_89 | AC | 468 ms
24,300 KB |
testcase_90 | TLE | - |
testcase_91 | TLE | - |
testcase_92 | TLE | - |
testcase_93 | AC | 359 ms
24,168 KB |
testcase_94 | AC | 801 ms
23,628 KB |
testcase_95 | TLE | - |
testcase_96 | TLE | - |
testcase_97 | TLE | - |
testcase_98 | AC | 648 ms
23,532 KB |
testcase_99 | AC | 458 ms
23,532 KB |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <unordered_set> #include <unordered_map> #include <random> #include <cmath> #include <cassert> #include <x86intrin.h> struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else // return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) // return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair<int, int> Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // enums // structs struct Pi_est { vector<int> n; vector<double> P; // 推定値 int t = 0; void init() { n.resize(25, 0); P.resize(25, 0.045); } void re_est(vector<bool> x) { t++; for (int xtmp = 0; xtmp < 25; xtmp++){ if (x[xtmp]) n[xtmp]++; } for (int xtmp = 0; xtmp < 25; xtmp++) { P[xtmp] = (double)n[xtmp] / (double)t; P[xtmp] = max(0.01, P[xtmp]); P[xtmp] = min(0.08, P[xtmp]); } return; } }; // constants constexpr int turn_limit = 1000; constexpr int field_height = 60; constexpr int field_width = 25; constexpr int player_initial_position = 12; constexpr int base_level = 1; constexpr int power_per_level = 100; constexpr double enemy_health_avg_base = 7.5; constexpr double enemy_health_avg_turn_factor = 0.15; constexpr double enemy_health_stddev_base = 1.5; constexpr double enemy_health_stddev_turn_factor = 0.03; constexpr double enemy_power_avg_health_factor = 0.8; constexpr double enemy_power_stddev_health_factor = 0.1; // inputs vector<vector<bool>> enemy_exist; vector<vector<int>> enemy_initial_health; vector<vector<int>> enemy_current_health; vector<vector<int>> enemy_power; // internals int turn_count = 0; int player_position = player_initial_position; int score = 0; int player_level = base_level; int power_gained = 0; Pi_est enemy_probability; inline bool within_board(int x, int y, int r, int c) { return 0 <= x && x < r && 0 <= y && y < c; } void init() { enemy_exist = vector<vector<bool>>(turn_limit + field_height, vector<bool>(field_width)); enemy_initial_health = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width)); enemy_current_health = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width)); enemy_power = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width)); enemy_probability.init(); } void receive_turn_input() { int enemy_num; cin >> enemy_num; if (enemy_num == -1) { // game over exit(0); } for (int i = 0; i < enemy_num; i++) { int h, p, x; cin >> h >> p >> x; enemy_exist[turn_count + field_height][x] = true; enemy_initial_health[turn_count + field_height][x] = h; enemy_current_health[turn_count + field_height][x] = h; enemy_power[turn_count + field_height][x] = p; } enemy_probability.re_est(enemy_exist[turn_count + field_height]); } int simulate_playout(char next_command) { auto enemy_exist = ::enemy_exist; auto enemy_initial_health = ::enemy_initial_health; auto enemy_current_health = ::enemy_current_health; auto enemy_power = ::enemy_power; auto turn_count = ::turn_count; auto player_position = ::player_position; auto score = ::score; auto player_level = ::player_level; auto power_gained = ::power_gained; bool is_next_turn = true; while (turn_count < turn_limit) { turn_count++; if (enemy_exist[turn_count][player_position]) { // game over break; } for (int i = 0; i < field_width; i++) { double roll = theRandom.nextDouble(); if (roll < enemy_probability.P[i]) { enemy_exist[turn_count + field_height - 1][i] = true; double enemy_health_avg = enemy_health_avg_base + enemy_health_avg_turn_factor * turn_count; double enemy_health_stddev = enemy_health_stddev_base + enemy_health_stddev_turn_factor * turn_count; enemy_initial_health[turn_count + field_height - 1][i] = max(1, (int) normal_distribution(enemy_health_avg, enemy_health_stddev)(theMersenne)); enemy_current_health[turn_count + field_height - 1][i] = enemy_initial_health[turn_count + field_height - 1][i]; double enemy_power_avg = enemy_power_avg_health_factor * enemy_initial_health[turn_count + field_height - 1][i]; double enemy_power_stddev = enemy_power_stddev_health_factor * enemy_initial_health[turn_count + field_height - 1][i]; enemy_power[turn_count + field_height - 1][i] = max(0, (int) normal_distribution(enemy_power_avg, enemy_power_stddev)(theMersenne)); } } if (is_next_turn) { if (next_command == 'L') player_position = (player_position - 1 + field_width) % field_width; else if (next_command == 'R') player_position = (player_position + 1) % field_width; is_next_turn = false; } else { } if (enemy_exist[turn_count][player_position]) { // game over break; } for (int x = turn_count; x < turn_count + field_height; x++) { if (enemy_exist[x][player_position]) { enemy_current_health[x][player_position] -= player_level; if (enemy_current_health[x][player_position] <= 0) { enemy_exist[x][player_position] = false; score += enemy_initial_health[x][player_position]; power_gained += enemy_power[x][player_position]; player_level = base_level + (power_gained / power_per_level); } break; } } } return score; } char decide_command() { const double time_limit = 0.00198 * (turn_count + 1); int iter_count = 0; ll score_l = 0; ll score_s = 0; ll score_r = 0; do { score_l += simulate_playout('L'); score_s += simulate_playout('S'); score_r += simulate_playout('R'); iter_count++; } while (theTimer.time() < time_limit); cerr << "turn_count = " << setw(3) << turn_count << ", iter_count = " << setw(4) << iter_count << ", score_l = " << setw(6) << score_l / iter_count << ", score_s = " << setw(6) << score_s / iter_count << ", score_r = " << setw(6) << score_r / iter_count << endl; cerr << player_level << " " << power_gained << endl; if (score_l > score_s && score_l > score_r) return 'L'; else if (score_s > score_r) return 'S'; else return 'R'; } void turn_action(char command) { cout << command << endl; turn_count++; if (command == 'L') player_position = (player_position - 1 + field_width) % field_width; else if (command == 'R') player_position = (player_position + 1) % field_width; for (int x = turn_count; x < turn_count + field_height; x++) { if (enemy_exist[x][player_position]) { enemy_current_health[x][player_position] -= player_level; if (enemy_current_health[x][player_position] <= 0) { enemy_exist[x][player_position] = false; score += enemy_initial_health[x][player_position]; power_gained += enemy_power[x][player_position]; player_level = base_level + (power_gained / power_per_level); } break; } } } void solve() { while (true) { receive_turn_input(); char command = decide_command(); turn_action(command); } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); init(); solve(); return 0; }