結果
問題 | No.5016 Worst Mayor |
ユーザー |
![]() |
提出日時 | 2023-04-29 01:42:47 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,170 bytes |
コンパイル時間 | 970 ms |
コンパイル使用メモリ | 98,260 KB |
実行使用メモリ | 24,444 KB |
スコア | 0 |
平均クエリ数 | 4.00 |
最終ジャッジ日時 | 2023-04-29 12:36:30 |
合計ジャッジ時間 | 7,898 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 50 |
ソースコード
#include <array>#include <cassert>#include <cmath>#include <iostream>#include <random>class xrand {uint64_t x;public:using result_type = uint32_t;static constexpr result_type min() {return std::numeric_limits<result_type>::min();}static constexpr result_type max() {return std::numeric_limits<result_type>::max();}xrand(uint64_t k) : x(k) {}xrand() : xrand(1) {}result_type operator()() {x ^= x << 9;x ^= x >> 7;return (x * 0x123456789abcdef) >> 32;}};xrand rng;std::uniform_int_distribution<> dist4(0, 3), dist14(0, 13);constexpr std::array<int, 4> dx{1, 0, -1, 0}, dy{0, 1, 0, -1};constexpr int N = 3000, T = 400;std::array<int, N> A, B, C, D;std::array<int, 26001> income;std::array<int, 14 * 14 * 14 * 14> cost;bool in_grid(unsigned x, unsigned y) { return x < 14 and y < 14; }int get_action() {int r = dist14(rng);if (r == 0) return 1;if (r == 1) return 3;return 2;}int main() {for (int i = 0; i <= 26; i++) {for (int j = 0; j <= 26000 / 223; j++) {int dist = 1000 * i + 223 * j;if (dist > 26000) break;income.at(dist) = 60 * j;}}cost.fill(26000);for (int i = 0; i < 196; i++) {cost.at(196 * i + i) = 0;}for (int x = 0; x < 14; x++) {for (int y = 0; y < 14; y++) {for (int dir = 0; dir < 4; dir++) {int z = x + dx[dir], w = y + dy[dir];if (not in_grid(z, w)) continue;cost.at(196 * (14 * x + y) + (14 * z + w)) = 1000;}}}for (int k = 0; k < 196; k++) {for (int i = 0; i < 196; i++) {for (int j = 0; j < 196; j++) {cost.at(196 * i + j) =std::min(cost.at(196 * i + j),cost.at(196 * i + k) + cost.at(196 * k + j));}}}int n, t;std::cin >> n >> t;for (int i = 0; i < N; i++) {std::cin >> A.at(i) >> B.at(i) >> C.at(i) >> D.at(i);A.at(i)--;B.at(i)--;C.at(i)--;D.at(i)--;}int64_t money = 1000000, collaborator = 1;for (int turn = 0; turn < T; turn++) {int64_t u, v;std::cin >> u >> v;assert(u == money);assert(v == collaborator);if (u == -1 and v == -1) {return 0;}int action = get_action();int dir, x, y, z, w;do {dir = dist4(rng);x = dist14(rng);y = dist14(rng);z = x + dx[dir];w = y + dy[dir];} while (not in_grid(z, w));if (action == 1) {std::cout << action << ' ' << x + 1 << ' ' << y + 1 << ' ' << z + 1<< ' ' << w + 1 << std::endl;} else {std::cout << action << std::endl;}if (action == 1) {int64_t d = 10000000 / sqrt(collaborator);assert(d * d * collaborator <= 100000000000000);assert((d + 1) * (d + 1) * collaborator > 100000000000000);money -= d;if (money < 0) {money = -1;collaborator = -1;continue;}cost.at(196 * (14 * x + y) + (14 * z + w)) = 223;cost.at(196 * (14 * z + w) + (14 * x + y)) = 223;for (int k = 0; k < 196; k++) {for (int i = 0; i < 196; i++) {for (int j = 0; j < 196; j++) {cost.at(196 * i + j) = std::min(cost.at(196 * i + j),cost.at(196 * i + k) + cost.at(196 * k + j));}}}} else if (action == 2) {collaborator++;} else {money += 50000;}for (int i = 0; i < N; i++) {money += income.at(cost.at(196 * (14 * A.at(i) + B.at(i)) +(14 * C.at(i) + D.at(i))));}}return 0;}