Submission #626793

#	Time	Username	Problem	Language	Result	Execution time	Memory
626793		welleyth	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	18 ms	1112 KiB

prison

#include "prison.h"

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

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> strategy(27,vector<int>(N+1,0));
    strategy[0][0] = 0;
    for(int i = 1; i <= N; i++){
        strategy[0][i] = ((i >> 13 & 1) + (13 << 1) - 1);
    }

    for(int i = 1; i <= 26; i++){
        int cur_pos = ((i+1) >> 1);
        int bt = (i+1) & 1;
        strategy[i][0] = cur_pos % 2;
        for(int j = 1; j <= N; j++){
            int bt2 = (j >> cur_pos & 1);
            if(bt2 > bt){
                strategy[i][j] = -(strategy[i][0]^1)-1;
            } else if(bt2 < bt){
                strategy[i][j] = -(strategy[i][0])-1;
            } else {
                if(cur_pos > 0){
                    if(cur_pos > 1)
                        strategy[i][j] = (((cur_pos-1) << 1) + (j >> (cur_pos-1) & 1)) - 1;
                    else {
                        if(j & 1)
                            strategy[i][j] = -(strategy[i][0]^1)-1;
                        else
                            strategy[i][j] = -(strategy[i][0])-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: 46 / 90