Submission #629319

#	Time	Username	Problem	Language	Result	Execution time	Memory
629319		two_sides	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1452 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

namespace {
    using namespace std;

    vector<int> base = {3, 3, 3, 3, 3, 2, 2, 1};

    vector<vector<int>> s;

    void gen(int pos, int cur, int l, int r) {
        s[cur][0] = pos & 1;
        s[cur][l] = -1 - (pos & 1);
        s[cur][r] = -2 + (pos & 1);
        if (l + 1 == r) return;
        int nxt = 1;
        for (int i = 0; i < pos; i++)
            nxt += base[i];
        for (int i = 0; i < base[pos]; i++) {
            s[nxt + i][l] = -2 + (pos & 1);
            s[nxt + i][r] = -1 - (pos & 1);
        }
        l++; r--;
        int len = (r - l + 1) / base[pos];
        for (int i = 0; i < base[pos]; i++) {
            for (int k = 0; k < len; k++)
                s[cur][l + k + len * i] = nxt + i;
            for (int j = 0; j < base[pos]; j++)
                if (i == j) gen(pos + 1, nxt + i,
                    l + len * i, l + len * (i + 1) - 1);
                else if (i < j) {
                    for (int k = 0; k < len; k++)
                        s[nxt + i][l + k + len * j] = -1 - (pos & 1);
                } else {
                    for (int k = 0; k < len; k++)
                        s[nxt + i][l + k + len * j] = -2 + (pos & 1);
                }
        }
    }
}

vector<vector<int>> devise_strategy(int n) {
    int m = 2;
    for (int i = 7; i >= 0; i--)
        m = m * base[i] + 2;
    s.resize(21);
    for (int i = 0; i <= 20; i++)
        s[i].resize(m + 1);
    gen(0, 0, 1, m);
    for (int i = 0; i <= 20; i++)
        s[i].resize(n + 1);
    return s;
}

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