Submission #630397

#	Time	Username	Problem	Language	Result	Execution time	Memory
630397		welleyth	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1016 KiB

prison

#include "prison.h"

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

constexpr int base = 3;

int getKth(int x,int k){
    while(k > 0){
        x /= base;
        k--;
    }
    return x % base;
}

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> strategy(23,vector<int>(N+1,0));
    strategy[0][0] = 0;
    for(int i = 1; i <= N; i++){
        strategy[0][i] = (base*7 + getKth(i,7)-1);
    }
    strategy[0][1] = -1;
    strategy[0][N] = -2;

    for(int i = 1; i <= 22; i++){
        int cur_pos = (i+1)/3;
        int bt = (i+1) % 3;
        strategy[i][0] = cur_pos % 2;
        if(i == 1){
            for(int j = 1; j <= N; j++){
                if(getKth(j,0) == 0)
                    strategy[i][j] = -(strategy[i][0])-1;
                else if(getKth(j,0) == 2)
                    strategy[i][j] = -(strategy[i][0]^1)-1;
                else
                    strategy[i][j] = 0;
            }
            continue;
        }
        for(int j = 1; j <= N; j++){
            int bt2 = getKth(j,cur_pos);
//            cerr << j << " " << bt2 << "\n";
            if(bt2 > bt){
                strategy[i][j] = -(strategy[i][0]^1)-1; /// cur is >
            } else if(bt2 < bt){
                strategy[i][j] = -(strategy[i][0])-1; /// cur is <
            } else {
                if(cur_pos > 0){
                    if(cur_pos > 1)
                        strategy[i][j] = (base * (cur_pos-1) + getKth(j,cur_pos-1)-1);
                    else {
                        /// 0,1,2
                        if(getKth(j,0) == 2)
                            strategy[i][j] = -(strategy[i][0]^1)-1;
                        else if(getKth(j,0) == 0)
                            strategy[i][j] = -(strategy[i][0])-1;
                        else
                            strategy[i][j] = 1;
                    }
                }
                else
                    strategy[i][j] = -1; /// cannot be
            }
        }
    }

    return strategy;
}
/**

5000
1 2
1 3
2 1
2 3
3 1
3 2
4096 4097
-1

**/

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