Submission #1247571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247571		fskarica	죄수들의 도전 (IOI22_prison)	C++20	56 / 100	8 ms	1860 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

int n;
vector <vector<int>> ret;
vector <int> v;

vector<std::vector<int>> devise_strategy(int N) {
    n = N;

    int bit = 1;
    while ((1 << (bit + 1)) <= n) {
        bit++;
    }

    v.clear();
    v.push_back(0);
    for (int i = 1; i <= n; i++) {
        if (i & (1 << bit)) v.push_back(2);
        else v.push_back(1);
    }
    ret.push_back(v);

    int m = bit * 2 + 3;
    for (int pos = 1; pos < m; pos += 2) {
        bit--;

        v.clear();
        v.push_back(((pos + 1) / 2) % 2);
        for (int i = 1; i <= n; i++) {
            if (i & (1 << (bit + 1))) {
                if (v[0] == 0) v.push_back(-2);
                else v.push_back(-1);
            }
            else {
                if (i & (1 << bit)) v.push_back(pos + 3);
                else v.push_back(pos + 2);
            }
        }
        ret.push_back(v);

        v.clear();
        v.push_back(((pos + 1) / 2) % 2);
        for (int i = 1; i <= n; i++) {
            if (!(i & (1 << (bit + 1)))) {
                if (v[0] == 0) v.push_back(-1);
                else v.push_back(-2);
            }
            else {
                if (i & (1 << bit)) v.push_back(pos + 3);
                else v.push_back(pos + 2);
            }
        }
        ret.push_back(v);
    }

    for (int i = 0; i < ret.size(); i++) {
        for (int j = 0; j < ret[i].size(); j++) {
            if (ret[i][j] >= (int)ret.size()) {
                ret[i][j] = -1;
            }
        }
    }

    return ret;
}

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