Submission #629770

#	Time	Username	Problem	Language	Result	Execution time	Memory
629770		spacewalker	Radio Towers (IOI22_towers)	C++17	Compilation error	0 ms	0 KiB

towers

#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
            int storedDigit = (state - 1) % 3;
            for (int oval = 1; oval <= N; ++oval) { // other value
                int otherDigit = getNthLSD(oval-1, L-layer);
                if (storedDigit != otherDigit) {
                    int storedLessOtherAns = DECLARE_A_LESS, storedGreaterOtherAns = DECLARE_B_LESS;
                    // if it's actually B that's stored, interchange the two
                    if (layer % 2 == 0) swap(storedLessOtherAns, storedGreaterOtherAns);
                    if (storedDigit > otherDigit) ans[state][oval] = storedGreaterOtherAns;
                    else ans[state][oval] = storedLessOtherAns;
                } else { // store the next digit and move states
                    // the two numbers are equal. this shouldn't happen
                    if (3 * layer + 1 == ans.size()) {
                        ans[state][oval] = 0;
                    } else {
                        int digitToStore = getNthLSD(oval-1, L-layer-1);
                        ans[state][oval] = digitToStore + 1 + 3 * layer;
                    }
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

towers.cpp:1:10: fatal error: prison.h: No such file or directory
    1 | #include "prison.h"
      |          ^~~~~~~~~~
compilation terminated.