Submission #821478

#TimeUsernameProblemLanguageResultExecution timeMemory
821478finn__Prisoner Challenge (IOI22_prison)C++17
0 / 100
4 ms468 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; constexpr int it[21] = {-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7}, part[21] = {-1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 0}, d[8] = {3, 3, 3, 3, 3, 2, 2, 1}, N_MAX = 5588; int get_part(pair<int, int> const &range, int n, int iteration) { return (n - (range.first + 1)) / d[iteration]; } pair<int, int> get_subrange(pair<int, int> const &range, int part, int iteration) { return {range.first + 1 + (part * (range.second - range.first - 1)) / d[iteration], range.first + ((part + 1) * (range.second - range.first - 1)) / d[iteration]}; } pair<int, int> reconstruct_range(int n, int iteration) { pair<int, int> range = {1, N_MAX}; for (int i = 0; i < iteration; ++i) { if (n == range.first || n == range.second) return {-1, -1}; // We will never reach this state. range = get_subrange(range, get_part(range, n, i), i); } return range; } int encode_state(int iteration, int part) { int state = 1; while (it[state] != iteration) ++state; return state + part; } vector<vector<int>> devise_strategy(int N) { vector<vector<int>> s(21, vector<int>(N + 1)); for (size_t i = 0; i <= 20; ++i) { s[i][0] = !(it[i] & 1); for (int j = 1; j <= N; ++j) { auto [a, b] = reconstruct_range(j, it[i]); if (a == -1 && b == -1) continue; // Check whether it's on the boundary of the common range. if (j == a) { s[i][j] = s[i][0] ? -2 : -1; continue; } if (j == b) { s[i][j] = s[i][0] ? -1 : -2; continue; } if (i) // In the first iteration, we don't have a subrange specified by the state. { int k = get_part({a, b}, j, it[i]); int h = part[i]; // If they don't belong to the same part of the subrange, stop. if (k != h) { s[i][j] = (s[i][0] ^ (k > h)) ? -2 : -1; continue; } tie(a, b) = get_subrange({a, b}, h, it[i]); // the other bag's range // Check whether it's on the boundary of the new range. if (j == a) { s[i][j] = s[i][0] ? -2 : -1; continue; } if (j == b) { s[i][j] = s[i][0] ? -1 : -2; continue; } } assert(it[i] < 7); s[i][j] = encode_state(it[i] + 1, get_part({a, b}, j, it[i] + 1)); } } return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...