# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
629771 | spacewalker | Prisoner Challenge (IOI22_prison) | C++17 | 1 ms | 300 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prison.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int CHECK_A = 0, CHECK_B = 1, DECLARE_A_LESS = -1, DECLARE_B_LESS = -2;
int layers(int N) {
if (N < 3) return 1;
else return 1 + layers(N / 3);
}
int getNthLSD(int N, int i) {
if (i == 0) return N % 3;
else return getNthLSD(N/3, i-1);
}
std::vector<std::vector<int>> devise_strategy(int N) {
// we need 3 log3(N) + 1 states
int L = layers(N-1);
vector<vector<int>> ans(3 * layers(N-1) + 1, vector<int>(N+1));
// 0 move to {1, 2, 3} depending on A's L-1th ternary digit
ans[0][0] = CHECK_A;
for (int aval = 1; aval <= N; ++aval) ans[0][aval] = getNthLSD(aval-1, L-1) + 1;
for (int layer = 1; 3 * layer <= ans.size(); ++layer) {
// if odd layer, A's digit is written
// if even layer, B's digit is written
for (int state = 3 * layer - 2; state < 3 * layer; ++state) {
ans[state][0] = (layer % 2 == 1 ? CHECK_B : CHECK_A); // check opposite number
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |