Submission #763696

#	Time	Username	Problem	Language	Result	Execution time	Memory
763696		raysh07	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	980 KiB

prison

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

vector <int> a = {1, 6, 20, 62, 188, 566, 1698, 5096};
int mv[22];
int v[22];

int get(int x, int b){
    for (int i = 1; i < b; i++){
        if (x == 0) return -3;
        if (x == a[i - 1] - 1) return -3;
        x--;
        x %= a[i];
    }
    
    if (x == 0) return -1;
    if (x == a[b - 1] - 1) return -2;
    x--;
    return x / a[b];
}
 
vector<vector<int>> devise_strategy(int n) {
    reverse(a.begin(), a.end());
    vector<vector<int>> ans(21, vector<int>(n + 1, 0));
    
    mv[0] = mv[1] = mv[2] = mv[3] = 1;
    mv[4] = mv[5] = mv[6] = 2;
    mv[7] = mv[8] = mv[9] = 3;
    mv[10] = mv[11] = mv[12] = 4;
    mv[13] = mv[14] = mv[15] = 5;
    mv[16] = mv[17] = mv[18] = 6;
    mv[19] = 7;
    mv[20] = 7;
    
    v[1] = v[4] = v[7] = v[10] = v[13] = v[16] = 0;
    v[2] = v[5] = v[8] = v[11] = v[14] = v[17] = 1;
    v[3] = v[6] = v[9] = v[12] = v[15] = v[18] = 2;
    
    for (int i = 0; i <= 20; i++){
        if (i == 0){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int xx = get(j, mv[i]);
                if (xx == -1) ans[i][j] = -1;
                else if (xx == -2) ans[i][j] = -2;
                else if (xx == -3) ans[i][j] = 0;
                else ans[i][j] = 1 + xx;
            }
        } else if (i == 19){
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int bb = get(j, mv[i]);
                if (bb == -1 || bb == 0) ans[i][j] = -2;
                else if (bb == -2 || bb == 3) ans[i][j] = -1;
                else ans[i][j] = 20;
            }
        } else if (i == 20){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int aa = get(j, mv[i]);
                if (aa == -1 || aa == 0 || aa == 1) ans[i][j] = -1;
                else ans[i][j] = -2;
            }
        } else if (i >= 16){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int aa = get(j, mv[i]);
                int bb = v[i];
                if (aa == -1) ans[i][j] = -1;
                else if (aa == -2) ans[i][j] = -2;
                else if (aa == -3) ans[i][j] = 0;
                else if (aa < bb) ans[i][j] = -1;
                else if (bb < aa) ans[i][j] = -2;
                else {
                    aa = get(j, mv[i] + 1);
                    if (aa == -1) ans[i][j] = -1;
                    else if (aa == -2) ans[i][j] = -2;
                    else if (aa == -3) ans[i][j] = 0;
                    else ans[i][j] = 19;
                }
            }
        } else if (i % 6 == 1 || i % 6 == 2 || i % 6 == 3) {
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int aa = v[i];
                int bb = get(j, mv[i]);
                if (bb == -1) ans[i][j] = -2;
                else if (bb == -2) ans[i][j] = -1;
                else if (bb == -3) ans[i][j] = 0;
                else if (aa < bb) ans[i][j] = -1;
                else if (bb < aa) ans[i][j] = -2;
                else {
                    bb = get(j, mv[i] + 1);
                    if (bb == -1) ans[i][j] = -2;
                    else if (bb == -2) ans[i][j] = -1;
                    else if (bb == -3) ans[i][j] = 0;
                    else ans[i][j] = i - v[i] + 3 + bb;
                }
            }
        } else {
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int aa = get(j, mv[i]);
                int bb = v[i];
                if (aa == -1) ans[i][j] = -1;
                else if (aa == -2) ans[i][j] = -2;
                else if (aa == -3) ans[i][j] = 0;
                else if (aa < bb) ans[i][j] = -1;
                else if (bb < aa) ans[i][j] = -2;
                else {
                    aa = get(j, mv[i] + 1);
                    if (aa == -1) ans[i][j] = -1;
                    else if (aa == -2) ans[i][j] = -2;
                    else if (aa == -3) ans[i][j] = 0;
                    else ans[i][j] = i - v[i] + 3 + aa;
                }
            }
        }
    }
    return ans;
}

// int main(){
//     int n; cin >> n;
//     auto ans = devise_strategy(n);
    
//     // for (auto x : ans){
//     //     for (auto y : x){
//     //         cout << y << " ";
//     //     }
//     //     cout << "\n";
//     // }
//     return 0;
// }

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