Submission #763551

#	Time	Username	Problem	Language	Result	Execution time	Memory
763551		raysh07	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	5 ms	596 KiB

prison

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

vector <int> a = {2501, 834, 279, 94, 32, 11, 4, 1};
int mv[22];
int v[22];

int get(int x, int b){
    for (int i = 0; i < b; i++){
        x %= a[i];
    }
    
    return x / a[b];
}
 
vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ans(22, vector<int>(n + 1));
    
    mv[0] = 0;
    mv[1] = mv[2] = 0;
    mv[3] = mv[4] = mv[5] = 1;
    mv[6] = mv[7] = mv[8] = 2;
    mv[9] = mv[10] = mv[11] = 3;
    mv[12] = mv[13] = mv[14] = 4;
    mv[15] = mv[16] = mv[17] = 5;
    mv[18] = mv[19] = mv[20] = 6;
    mv[21] = 7;
    
    v[1] = v[3] = v[6] = v[9] = v[12] = v[15] = v[18] = 0;
    v[2] = v[4] = v[7] = v[10] = v[13] = v[16] = v[19] = 1;
    v[5] = v[8] = v[11] = v[14] = v[17] = v[20] = 2;
    
    for (int i = 0; i <= 21; i++){
        if (i == 0){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                ans[i][j] = 1 + get(j, mv[i]);
            }
            continue;
        } else if (i == 21){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int x = get(j, mv[i]);
                if (x <= 1) ans[i][j] = -1;
                else ans[i][j] = -2;
            }
            continue;
        } else if (i <= 2){
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int bb = get(j, mv[i]);
                int aa = v[i];
                
                if (aa < bb) ans[i][j] = -1;
                else if (aa > bb) ans[i][j] = -2;
                else ans[i][j] = 3 + get(j, mv[i] + 1);
            }
            continue;
        } else if (i >= 18){
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int bb = get(j, mv[i]);
                int aa = v[i];
                
                if (aa < bb) ans[i][j] = -1;
                else if (aa > bb) ans[i][j] = -2;
                else {
                    int gg = get(j, mv[i] + 1);
                    if (gg == 0) ans[i][j] = -2;
                    else if (gg == 3) ans[i][j] = -1;
                    else ans[i][j] = 21;
                }
            }
            continue;
        }
        
        if (mv[i] & 1){
            //B's move
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int bb = get(j, mv[i]);
                int aa = v[i];
                
                if (aa < bb) ans[i][j] = -1;
                else if (aa > bb) ans[i][j] = -2;
                else ans[i][j] = i - v[i] + 3 + get(j, mv[i] + 1);
            }
        } else {
            //A's move 
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int aa = get(j, mv[i]);
                int bb = v[i];
                
                if (aa < bb) ans[i][j] = -1;
                else if (aa > bb) ans[i][j] = -2;
                else ans[i][j] = i - v[i] + 3 + get(j, mv[i] + 1);
            }
        }
    }
    
    for (int i = 0; i <= 21; i++){
        for (int j = 0; j <= n; j++){
            if (ans[i][j] < -2 || ans[i][j] > 21){
                assert(false);
            }
        }
    }
    
    // for (auto x : ans){
    //     for (auto y : x ) cout << y << " ";
    //     cout << "\n";
    // }
    
    // for (int i = 0; i <= x; i++){
    //     cout << i << " ";
    //     for (int j = 0; j <= n; j++){
    //         cout << ans[i][j] << " ";
    //     }
    // }
    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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 90