Submission #762212

#	Time	Username	Problem	Language	Result	Execution time	Memory
762212		raysh07	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1068 KiB

prison

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

int fetch(int x, int b){
    if (b == 0) return x % 3;
    else return fetch(x/3, b - 1);
}

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ans(23, vector<int>(n + 1));
    
    for (int i = 0; i <= 22; i++){
        if (i == 0){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                ans[i][j] = 1 + fetch(j, 7);
            }
        } else if (i == 22){
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                if (j % 3 == 0) ans[i][j] = -1;
                else if (j % 3 == 2) ans[i][j] = -2;
                else ans[i][j] = 0;
            }
        } else if (i % 6 == 1 || i % 6 == 2 || i % 6 == 3){
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++){
                int bit = 7 - (i - 1) / 3;
                
                int b = fetch(j, bit);
                int a = (i % 6) - 1;
                
                if (a > b) ans[i][j] = -2;
                else if (a < b) ans[i][j] = -1;
                else {
                    bit--;
                    if (bit == 0){
                        if (fetch(j, bit) == 0) ans[i][j] = -2;
                        else if (fetch(j, bit) == 2) ans[i][j] = -1;
                        else ans[i][j] = 22;
                    } else {
                        int x = i - i % 6;
                        x += 4;
                        ans[i][j] = x + fetch(j, bit);
                    }
                }
            }
        } else {
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++){
                int bit = 7 - (i - 1) / 3;
                
                int a = fetch(j, bit);
                int b = (i - 4) % 6;
                
                if (a > b) ans[i][j] = -2;
                else if (a < b) ans[i][j] = -1;
                else {
                    bit--;
                    int x = i + 1;
                    if (i % 6 == 5) x++;
                    if (i % 6 == 4) x+= 2;
                    
                    ans[i][j] = x + fetch(j, bit);
                }
            }
        }
    }
    
    
    // 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;
}

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