Submission #831998

#	Time	Username	Problem	Language	Result	Execution time	Memory
831998		dxz05	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1032 KiB

prison

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

using namespace std;

int get(int num, int pos, int base){
    while (pos--) num /= base;
    return num % base;
}

int state[20][10];
pair<int, int> meaning[200];

vector<vector<int>> devise_strategy(int N) {
    const int X = 22;

    vector<vector<int>> s(X + 1, vector<int>(N + 1, 0));

    state[0][1] = 1;
    meaning[1] = make_pair(0, 1);

    int nxt = 2;
    for (int i = 1; i <= 7; i++){
        for (int j = 0; j < 3; j++){
            meaning[nxt] = make_pair(i, j);
            state[i][j] = nxt++;
        }
    }

    s[0][0] = 1;
    for (int i = 1; i <= N; i++){
        s[0][i] = state[7][get(i, 7, 3)];
    }

    for (int i = 1; i <= X; i++){
        auto [b, r] = meaning[i];

        int bag = (7 - b) % 2;

        s[i][0] = bag;

        for (int j = 1; j <= N; j++){
            int d = get(j, b, 3);

            if (d < r){
                s[i][j] = (bag == 0 ? -1 : -2);
            } else if (d > r){
                s[i][j] = (bag == 0 ? -2 : -1);
            } else if (b > 0){
                int pd = get(j, b - 1, 3);

                if (b == 1){
                    if (pd == 0){
                        s[i][j] = (bag == 0 ? -1 : -2);
                    } else if (pd == 2){
                        s[i][j] = (bag == 0 ? -2 : -1);
                    } else {
                        s[i][j] = state[0][1];
                    }
                } else {
                    s[i][j] = state[b - 1][pd];
                }
            }
        }

    }

    return s;
}

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