Submission #639856

#	Time	Username	Problem	Language	Result	Execution time	Memory
639856		SlavicG	Prisoner Challenge (IOI22_prison)	C++17	54.50 / 100	13 ms	1236 KiB

prison

#include "prison.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

vector<vector<int>> devise_strategy(int n) {
    int x = 27;
    vector<vector<int>> a(x + 1, vector<int>(n + 1, 0));
    a[0][0] = 0;
    for(int i = 1; i <= n; ++i) {
        if(i >> 12 & 1) {
            a[0][i] = 27;
        } else a[0][i] = 26;
    }
    for(int i = 27; i >= 2; --i) {
        int bit = i / 2 - 1;
        if(bit % 2 == 0) {
            //did a now looking at b;
            a[i][0] = 1;
            for(int j = 1; j <= n; ++j) {
                if(j >> bit & 1) {
                    if(i % 2 == 0) {
                        a[i][j] = -1;
                    } else {
                        a[i][j] = (bit - 1) * 2 + (j >> (bit - 1) & 1) + 2;
                    }
                } else {
                    if(i % 2 == 1) {
                        a[i][j] = -2;
                    } else {
                        a[i][j] = (bit - 1) * 2 + (j >> (bit - 1) & 1) + 2;
                    }
                }
            }
        } else {
            //did b now looking at a
            a[i][0] = 0;
            for(int j = 1; j <= n; ++j) {
                if(j >> bit & 1) {
                    if(i % 2 == 0) {
                        a[i][j] = -2;
                    } else {
                        a[i][j] = (bit - 1) * 2 + (j >> (bit - 1) & 1) + 2;
                    }
                } else {
                    if(i % 2 == 1) {
                        a[i][j] = -1;
                    } else {
                        a[i][j] = (bit - 1) * 2 + (j >> (bit - 1) & 1) + 2;
                    }
                }
            }
        }
    }
    return a;
}

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