Submission #631861

#	Time	Username	Problem	Language	Result	Execution time	Memory
631861		CodePlatina	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1364 KiB

prison

#include "prison.h"

#include <vector>

using namespace std;

vector<vector<int>> V;

void f(int x, int l, int r, int t)
{
    if(l + 1 >= r) return;
    for(int y = x; y <= 20; ++y) V[y][l] = -1 - V[y][0], V[y][r - 1] = -2 + V[y][0];
    ++l; --r;
    if(l == r) return;

    int c;
    if(t == 19) c = 2;
    else c = 3;

    for(int i = 0; i < c; ++i)
    {
        int s = ((c - i) * l + i * r) / c, e = ((c - i - 1) * l + (i + 1) * r) / c;
        for(int j = s; j < e; ++j) V[x][j] = t + i;
        for(int j = l; j < s; ++j) V[t + i][j] = -2 + V[x][0];
        for(int j = e; j < r; ++j) V[t + i][j] = -1 - V[x][0];
        f(t + i, s, e, t + c);
    }
}

vector<vector<int>> devise_strategy(int N)
{
    int x = 20;
    V = vector<vector<int>>(x + 1, vector<int>(N + 1));
    V[0][0] = 0;
    V[1][0] = 1;
    V[2][0] = 1;
    V[3][0] = 1;
    V[4][0] = 0;
    V[5][0] = 0;
    V[6][0] = 0;
    V[7][0] = 1;
    V[8][0] = 1;
    V[9][0] = 1;
    V[10][0] = 0;
    V[11][0] = 0;
    V[12][0] = 0;
    V[13][0] = 1;
    V[14][0] = 1;
    V[15][0] = 1;
    V[16][0] = 0;
    V[17][0] = 0;
    V[18][0] = 0;
    V[19][0] = 1;
    V[20][0] = 1;
    f(0, 1, N + 1, 1);
    return V;
}

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