Submission #1235116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235116		Ghulam_Junaid	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1156 KiB

prison

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

int digit(int x, int i){
    for (int j = 0; j < 7 - i; j ++)
        x /= 3;
    return x % 3;
}

int ceil(int x, int y){
    return (x / y + ((x % y) > 0));
}

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> res;
    res.resize(23);
    for (int i = 0; i < 23; i ++){
        res[i].resize(n + 1);
        if (ceil(i, 3) % 2 == 0) res[i][0] = 0;
        else res[i][0] = 1;

        if (i == 22){
            for (int j = 1; j <= n; j ++){
                if (j % 3 == 0)
                    res[i][j] = -1 -(ceil(i, 3) % 2);
                else 
                    res[i][j] = -3 -(-1 -(ceil(i, 3) % 2));
            }
            break;
        }

        int cur = ceil(i, 3);
        // cout << i << " :: " << res[i][0] << " " << cur << endl;
        for (int j = 1; j <= n; j ++){
            int nxt = digit(j, cur);
            // cout << "put digit = " << nxt << endl;
            if (cur == 0){
                res[i][j] = 1 + nxt;
                continue;
            }
            int pw = 1;
            for (int jj = 0; jj < 8 - cur; jj ++, pw *= 3);

            int curd = digit(j, cur - 1);
            int rem = j % pw;
            int prvd = (i - 1) % 3;
            if (curd < prvd or (curd == prvd and rem == 0))
                res[i][j] = -1 -(ceil(i, 3) % 2);
            else if (curd > prvd or (curd == prvd and rem == pw - 1))
                res[i][j] = -3 -(-1 -(ceil(i, 3) % 2));
            else
                res[i][j] = 1 + nxt + 3 * cur;
            // cout << j << " : " << res[i][j] << endl;
            if (res[i][j] == 23) res[i][j] = 22;
        }
    }
    return res;
}

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