Submission #629773

#	Time	Username	Problem	Language	Result	Execution time	Memory
629773		spacewalker	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	20 ms	1068 KiB

prison

#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)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:26:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int layer = 1; 3 * layer <= ans.size(); ++layer) {
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
prison.cpp:42:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                     if (3 * layer + 1 == ans.size()) {
      |                         ~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 55 / 90