Submission #1164634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164634		SmuggingSpun	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	6 ms	1096 KiB

prison

#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
vector<vector<int>>devise_strategy(int n){
    vector<vector<int>>s;
    function<void(int, int, int, int, int, int)>solve;
    solve = [&] (int depth, int id, int l, int r, int L, int R){
        if(l > r){
            return;
        }
        while(s.size() <= id){
            s.emplace_back(vector<int>(n + 1, 0));
        }
        s[id][0] = depth & 1;
        for(int i = l++; i >= L; i--){
            s[id][i] = -s[id][0] - 1;
        }
        for(int i = r--; i <= R; i++){
            s[id][i] = -(s[id][0] ^ 1) - 1;
        }
        if(l > r){
            return;
        }
        if(depth < 4){
            int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3; 
            for(int i = l; i <= r; i++){
                if(i <= m1){
                    s[id][i] = depth * 3 + 1;
                }
                else if(i <= m2){
                    s[id][i] = depth * 3 + 2;
                }
                else{
                    s[id][i] = (depth + 1) * 3;
                }
            }
            solve(depth + 1, depth * 3 + 1, l, m1, l - 1, r + 1);
            solve(depth + 1, depth * 3 + 2, m1 + 1, m2, l - 1, r + 1);
            solve(depth + 1, depth * 3 + 3, m2 + 1, r, l - 1, r + 1);
        }
        else{
            int m = (l + r) >> 1;
            for(int i = l; i <= r; i++){
                if(i <= m){
                    s[id][i] = 13 + ((depth - 4) << 1);
                }
                else{
                    s[id][i] = 14 + ((depth - 4) << 1);
                }
            }
            solve(depth + 1, 13 + ((depth - 4) << 1), l, m, l - 1, r + 1);
            solve(depth + 1, 14 + ((depth - 4) << 1), m + 1, r, l - 1, r + 1);
        }
    };
    solve(0, 0, 1, n, 1, n);
    for(int i = 0; i < s.size(); i++){
        for(int j = 1; j <= n; j++){
            minimize(s[i][j], int(s.size()) - 1);
        }
    }
    return s;
}   

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