Submission #651457

#	Time	Username	Problem	Language	Result	Execution time	Memory
651457		Lobo	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	17 ms	1204 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()

const int maxn = 1e5+10;
const int inf = 1e9+10;

vector<vector<int>> devise_strategy(int N) {
    int B = 12;
    vector<vector<int>> ans(2*B+3);
    for(int i = 0; i <= 2*B+2; i++) ans[i].resize(N+1);
    ans[0][0] = B%2;
    for(int i = 1; i <= N; i++) {
        if((1<<B)&i) ans[0][i] = 2*B+1;
        else ans[0][i] = 2*B+2;
    }

    for(int i = 0; i <= B; i++) {
        if(i%2 == 0) {
            ans[2*i+1][0] = ans[2*i+2][0] = 1;
            // vejo o B
            for(int j = 1; j <= N; j++) {
                if(((1<<i)&j) != 0 && (i != 0 && ((1<<(i-1))&j) != 0)) {
                    // A tem i, B tem i, B tem i-1
                    ans[2*i+1][j] = 2*(i-1)+1; 
                    // A nao tem i, B tem i, B tem i-1
                    ans[2*i+2][j] = -1;
                }
                if(((1<<i)&j) != 0 && (i == 0 || ((1<<(i-1))&j) == 0)) {
                    // A tem i, B tem i, B nao tem i-1
                    ans[2*i+1][j] = 2*(i-1)+2; 
                    // A nao tem i, B tem i, B nao tem i-1
                    ans[2*i+2][j] = -1;
                }
                if(((1<<i)&j) == 0 && (i != 0 && ((1<<(i-1))&j) != 0)) {
                    // A tem i, B nao tem i, B tem i-1
                    ans[2*i+1][j] = -2; 
                    // A nao tem i, B nao tem i, B tem i-1
                    ans[2*i+2][j] = 2*(i-1)+1;
                }
                if(((1<<i)&j) == 0 && (i == 0 || ((1<<(i-1))&j) == 0)) {
                    // A tem i, B nao tem i, B nao tem i-1
                    ans[2*i+1][j] = -2; 
                    // A nao tem i, B nao tem i, B nao tem i-1
                    ans[2*i+2][j] = 2*(i-1)+2;
                }
            }
        }
        else {
            ans[2*i+1][0] = ans[2*i+2][0] = 0;
            // vejo o A
            for(int j = 1; j <= N; j++) {
                if(((1<<i)&j) != 0 && (i != 0 && ((1<<(i-1))&j) != 0)) {
                    // A tem i, B tem i, B tem i-1
                    ans[2*i+1][j] = 2*(i-1)+1; 
                    // A nao tem i, B tem i, B tem i-1
                    ans[2*i+2][j] = -2;
                }
                if(((1<<i)&j) != 0 && (i == 0 || ((1<<(i-1))&j) == 0)) {
                    // A tem i, B tem i, B nao tem i-1
                    ans[2*i+1][j] = 2*(i-1)+2; 
                    // A nao tem i, B tem i, B nao tem i-1
                    ans[2*i+2][j] = -2;
                }
                if(((1<<i)&j) == 0 && (i != 0 && ((1<<(i-1))&j) != 0)) {
                    // A tem i, B nao tem i, B tem i-1
                    ans[2*i+1][j] = -1; 
                    // A nao tem i, B nao tem i, B tem i-1
                    ans[2*i+2][j] = 2*(i-1)+1;
                }
                if(((1<<i)&j) == 0 && (i == 0 || ((1<<(i-1))&j) == 0)) {
                    // A tem i, B nao tem i, B nao tem i-1
                    ans[2*i+1][j] = -1; 
                    // A nao tem i, B nao tem i, B nao tem i-1
                    ans[2*i+2][j] = 2*(i-1)+2;
                }
            }
        }
    }
    return ans;
}

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