Submission #627195

#	Time	Username	Problem	Language	Result	Execution time	Memory
627195		TranGiaHuy1508	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	16 ms	980 KiB

prison

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

#include "prison.h"

int MAXNUM = 22;
int pow3[8] = {1, 3, 9, 27, 81, 243, 729, 2187};

vector<vector<int>> devise_strategy(int N){
    vector<vector<int>> res(MAXNUM + 1, vector<int>(N+1));

    for (int i = 0; i <= MAXNUM; i++){
        int type = (i + 2) / 3;
        int AB = type & 1;

        res[i][0] = AB;
        int cntbit[2] = {type, type};
        if (type) cntbit[AB]--;

        int oldbit = (i + 2) % 3;

        for (int j = 1; j <= N; j++){
            if (i == 0){
                res[i][j] = (j / pow3[7]) % 3 + 1;
            }
            else if (i == 22){
                int bit1 = j % 3;
                if (bit1 == 0) res[i][j] = -1;
                else res[i][j] = -2;
            }
            else if (i >= 19){
                int bit1 = (j / 3) % 3, bit2 = j % 3;
                if (bit1 < oldbit) res[i][j] = (AB ? -2 : -1);
                else if (bit1 > oldbit) res[i][j] = (AB ? -1 : -2);
                else if (bit2 == 0) res[i][j] = -2;
                else if (bit2 == 2) res[i][j] = -1;
                else res[i][j] = 22;
            }
            else{
                int bit1 = (j / pow3[7 - cntbit[AB]]) % 3, bit2 = (j / pow3[6 - cntbit[AB]]) % 3;
                if (bit1 < oldbit) res[i][j] = (AB ? -2 : -1);
                else if (bit1 > oldbit) res[i][j] = (AB ? -1 : -2);
                else{
                    res[i][j] = ((type + 1) * 3 - 2) + bit2;
                }
            }
        }
    }

    return res;
}

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