Submission #1080673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080673		asdasdqwer	Prisoner Challenge (IOI22_prison)	C++17	50 / 100	12 ms	1372 KiB

prison

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

std::vector<std::vector<int>> devise_strategy(int N) {
    int s = 30;
    vector<vector<int>> strat(s+1, vector<int>(N+1, 0));
    for (int i=0;i<=5;i++) {
        strat[i][0] = 0;
        int pos = (6-i) * 2 - 1;

        for (int j=1;j<=N;j++) {
            int res = ((j >> pos) & 3);
            strat[i][j] = 6 + i*4 + res;
        }
    }

    for (int i=6;i<=29;i++) {
        int pos = (6 - ((i - 6) / 4)) * 2 - 1;
        strat[i][0] = 1;
        int rem = (i-6) % 4;

        for (int j=1;j<=N;j++) {
            int res = ((j >> pos) & 3);
            if (res > rem) {
                strat[i][j] = -1;
            }

            else if (res < rem) {
                strat[i][j] = -2;
            }

            else {
                strat[i][j] = ((i-6)/4)+1;
                if (strat[i][j] == 6) strat[i][j] = 30;
            }
        }
    }

    strat[30][0]=0;
    for (int i=1;i<=N;i++) {
        if ((i & 1) == 1) {
            strat[30][i] = -2;
        }

        else strat[30][i] = -1;
    }

    return strat;
}

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