Submission #1073395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073395		Zicrus	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	7 ms	1156 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;

typedef long long ll;

int n;

vector<vector<int>> devise_strategy(int N) {
    n = N;
    int x = 22;
    vector<vector<int>> res(x+1, vector<int>(n+1));
    res[0][0] = 0;
    for (int j = 1; j <= n; j++) {
        int k = (int)pow(3, 7);
        res[0][j] = j/k + 1;
    }
    for (int i1 = 1; i1 <= x-1; i1++) {
        int i = i1-1;
        bool checkA = (i/3)&1;
        int pos = 7-(i/3);
        int k = (int)pow(3, pos);
        res[i1][0] = !checkA;
        if (pos <= 1) {
            for (int j = 1; j <= n; j++) {
                int t = (j/k)%3;
                if (t != i%3) {
                    res[i1][j] = t > i%3 ? -1-(int)checkA : -2+(int)checkA;
                    continue;
                }
                t = (j*3/k)%3;
                if (t == 0) {
                    res[i1][j] = -2;
                }
                else if (t == 2) {
                    res[i1][j] = -1;
                }
                else {
                    res[i1][j] = 3*(i/3 + 1) + 1;
                }
            }
        }
        else {
            for (int j = 1; j <= n; j++) {
                int t = (j/k)%3;
                if (t != i%3) {
                    res[i1][j] = t > i%3 ? -1-(int)checkA : -2+(int)checkA;
                    continue;
                }
                t = (j*3/k)%3;
                res[i1][j] = 3*(i/3 + 1) + t + 1;
            }
        }
    }
    res[x][0] = 0;
    for (int j = 1; j <= n; j++) {
        if (j%3 == 0) res[x][j] = -1;
        else res[x][j] = -2;
    }
    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

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