結果
問題 | No.5016 Worst Mayor |
ユーザー | trineutron |
提出日時 | 2023-04-29 10:36:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,936 bytes |
コンパイル時間 | 902 ms |
コンパイル使用メモリ | 98,040 KB |
実行使用メモリ | 25,936 KB |
スコア | 0 |
最終ジャッジ日時 | 2023-04-29 12:37:38 |
合計ジャッジ時間 | 7,506 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
ソースコード
#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;constexpr bool in_grid(unsigned x, unsigned y) { return x < 14 and y < 14; }constexpr int id(unsigned x, unsigned y) { return 14 * x + y; }constexpr int id4(unsigned x, unsigned y, unsigned z, unsigned w) {return 2744 * x + 196 * y + 14 * z + w;}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;}}for (int x = 0; x < 14; x++) {for (int y = 0; y < 14; y++) {for (int z = 0; z < 14; z++) {for (int w = 0; w < 14; w++) {cost.at(id4(x, y, z, w)) = 1000 * (abs(x - z) + abs(y - w));}}}}int64_t income_turn = 0, income_next = 0;int x, y, z, w;auto road_next = [&]() {for (int i = 0; i < 14; i++) {for (int j = 0; j < 14; j++) {for (int dir = 0; dir < 4; dir++) {int k = i + dx[dir], l = j + dy[dir];if (not in_grid(k, l)) continue;int count = 0;for (int person = 0; person < N; person++) {int a = A.at(person), b = B.at(person),c = C.at(person), d = D.at(person);int distance = cost.at(id4(a, b, c, d));distance = std::min(distance,cost.at(id4(a, b, i, j) + 223 + id4(k, l, c, d)));distance = std::min(distance,cost.at(id4(a, b, k, l) + 223 + id4(i, j, c, d)));count += income.at(distance);}if (count > income_next) {income_next = count;x = i;y = j;z = k;w = l;}}}}};road_next();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;}int64_t d = 10000000 / sqrt(collaborator);assert(d * d * collaborator <= 100000000000000);assert((d + 1) * (d + 1) * collaborator > 100000000000000);int action = 1;if (turn < 99) {action = 2;} else if (money < d) {action = 3;}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) {money -= d;if (money < 0) {money = -1;collaborator = -1;continue;}int k = id(x, y), l = id(z, w);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) + 223 + cost.at(196 * l + j));cost.at(196 * i + j) = std::min(cost.at(196 * i + j),cost.at(196 * i + l) + 223 + cost.at(196 * k + j));}}income_turn = income_next;road_next();} else if (action == 2) {collaborator++;} else {money += 50000;}money += income_turn;}return 0;}