Submission #736295

#	Time	Username	Problem	Language	Result	Execution time	Memory
736295		math_rabbit_1028	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	928 KiB

prison

#include "prison.h"
#include <vector>
using namespace std;

int X = 0;
void findx(int st, int ed, int v) {
    if (ed - st == 0) {
        X = max(X, v);
        return;
    }
    if (ed - st == 1) {
        X = max(X, v);
        return;
    }
    if (ed - st == 2) {
        X = max(X, ((v+2)/3)*3 + 1);
        return;
    }
    if (ed - st == 3) {
        X = max(X, ((v+2)/3)*3 + 1);
        return;
    }
    if (ed - st == 4) {
        X = max(X, ((v+2)/3)*3 + 2);
        return;
    }
    if (ed - st == 5) {
        X = max(X, ((v+2)/3)*3 + 2);
        return;
    }
    else {
        int x = st + (ed - st) / 3, y = st + ((ed - st) / 3) * 2;
        findx(st + 1, x, ((v+2)/3)*3 + 1);
        findx(x + 1, y, ((v+2)/3)*3 + 2);
        findx(y + 1, ed - 1, ((v+2)/3)*3 + 3);
    }
}

void solve(vector< vector<int> > &ans, int st, int ed, int v, int bef) {
    int now;
    if (bef == -2) now = -1;
    else now = -2;

    if (ed - st == 0) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        return;
    }
    if (ed - st == 1) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        ans[v][st + 1] = (bef);
        return;
    }
    if (ed - st == 2) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        ans[v][st + 1] = (((v+2)/3)*3 + 1);
        ans[v][st + 2] = (bef);

        ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 1][st + 0] = (bef);
        ans[((v+2)/3)*3 + 1][st + 1] = (bef);
        ans[((v+2)/3)*3 + 1][st + 2] = (now);

        return;
    }
    if (ed - st == 3) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        ans[v][st + 1] = (((v+2)/3)*3 + 1);
        ans[v][st + 2] = (((v+2)/3)*3 + 1);
        ans[v][st + 3] = (bef);

        ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 1][st + 0] = (bef);
        ans[((v+2)/3)*3 + 1][st + 1] = (bef);
        ans[((v+2)/3)*3 + 1][st + 2] = (now);
        ans[((v+2)/3)*3 + 1][st + 3] = (now);

        return;
    }
    if (ed - st == 4) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        ans[v][st + 1] = (((v+2)/3)*3 + 1);
        ans[v][st + 2] = (((v+2)/3)*3 + 1);
        ans[v][st + 3] = (((v+2)/3)*3 + 2);
        ans[v][st + 4] = (bef);

        ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 1][st + 0] = (bef);
        ans[((v+2)/3)*3 + 1][st + 1] = (bef);
        ans[((v+2)/3)*3 + 1][st + 2] = (now);
        ans[((v+2)/3)*3 + 1][st + 3] = (now);
        ans[((v+2)/3)*3 + 1][st + 4] = (now);

        ans[((v+2)/3)*3 + 2][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 2][st + 0] = (bef);
        ans[((v+2)/3)*3 + 2][st + 1] = (bef);
        ans[((v+2)/3)*3 + 2][st + 2] = (bef);
        ans[((v+2)/3)*3 + 2][st + 3] = (bef);
        ans[((v+2)/3)*3 + 2][st + 4] = (now);

        return;
    }
    if (ed - st == 5) {
        ans[v][0] = (-1 - now);
        ans[v][st + 0] = (now);
        ans[v][st + 1] = (((v+2)/3)*3 + 1);
        ans[v][st + 2] = (((v+2)/3)*3 + 1);
        ans[v][st + 3] = (((v+2)/3)*3 + 2);
        ans[v][st + 4] = (((v+2)/3)*3 + 2);
        ans[v][st + 5] = (bef);

        ans[((v+2)/3)*3 + 1][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 1][st + 0] = (bef);
        ans[((v+2)/3)*3 + 1][st + 1] = (bef);
        ans[((v+2)/3)*3 + 1][st + 2] = (now);
        ans[((v+2)/3)*3 + 1][st + 3] = (now);
        ans[((v+2)/3)*3 + 1][st + 4] = (now);
        ans[((v+2)/3)*3 + 1][st + 5] = (now);

        ans[((v+2)/3)*3 + 2][0] = (-1 - bef);
        ans[((v+2)/3)*3 + 2][st + 0] = (bef);
        ans[((v+2)/3)*3 + 2][st + 1] = (bef);
        ans[((v+2)/3)*3 + 2][st + 2] = (bef);
        ans[((v+2)/3)*3 + 2][st + 3] = (bef);
        ans[((v+2)/3)*3 + 2][st + 4] = (now);
        ans[((v+2)/3)*3 + 2][st + 5] = (now);

        return;
    }
    else {
        ans[v][0] = (-1 - now);
        int x = st + (ed - st) / 3, y = st + ((ed - st) / 3) * 2;
        ans[v][st] = (now);
        ans[v][ed] = (bef);
        for (int i = st + 1; i <= x; i++) {
            ans[v][i] = (((v+2)/3)*3 + 1);
        }
        for (int i = x + 1; i <= y; i++) {
            ans[v][i] = (((v+2)/3)*3 + 2);
        }
        for (int i = y + 1; i < ed; i++) {
            ans[v][i] = (((v+2)/3)*3 + 3);
        }

        ans[((v+2)/3)*3 + 1][st] = (bef);
        for (int i = x + 1; i < ed; i++) {
            ans[((v+2)/3)*3 + 1][i] = (now);
        }
        ans[((v+2)/3)*3 + 1][ed] = (now);
        solve(ans, st + 1, x, ((v+2)/3)*3 + 1, now);

        ans[((v+2)/3)*3 + 2][st] = (bef);
        for (int i = st + 1; i <= x; i++) {
            ans[((v+2)/3)*3 + 2][i] = (bef);
        }
        for (int i = y; i < ed; i++) {
            ans[((v+2)/3)*3 + 2][i] = (now);
        }
        ans[((v+2)/3)*3 + 2][ed] = (now);
        solve(ans, x + 1, y, ((v+2)/3)*3 + 2, now);

        ans[((v+2)/3)*3 + 3][st] = (bef);
        for (int i = st + 1; i <= y; i++) {
            ans[((v+2)/3)*3 + 3][i] = (bef);
        }
        ans[((v+2)/3)*3 + 3][ed] = (now);
        solve(ans, y + 1, ed - 1, ((v+2)/3)*3 + 3, now);
    }
}

vector< vector<int> > devise_strategy(int N) {
    vector< vector<int> > ans;
    findx(1, N, 0);
    for (int i = 0; i <= X; i++) {
        vector<int> temp;
        for (int j = 0; j <= N; j++) temp.push_back(0);
        ans.push_back(temp);
    }
    solve(ans, 1, N, 0, -2);
    return ans;
}

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