Submission #627241

#	Time	Username	Problem	Language	Result	Execution time	Memory
627241		phathnv	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	16 ms	996 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

/*
x -> 2
2 -> 6
2 -> 14
2 -> 30
2 -> 62
3 -> 188
3 -> 566
3 -> 1700
3 -> 5102
*/

void gen(int ord, int num, int l, int r, vector<vector<int>> &strat, const vector<int>& a) {
    if (ord == (int) a.size()) {
        assert(l + 1 == r);
        strat[num][0] = ord % 2;
        strat[num][l] = (ord % 2 == 0? -1 : -2);
        strat[num][r] = (ord % 2 == 0? -2 : -1);
        return;
    }

    int offset = 1;
    for (int i = 0; i < ord; ++i) {
        offset += a[i];
    }
    strat[num][0] = ord % 2;
    strat[num][l] = (ord % 2 == 0? -1 : -2);
    strat[num][r] = (ord % 2 == 0? -2 : -1);
    for (int i = 0; i < a[ord]; ++i) {
        strat[offset + i][l] = (ord % 2 == 0? -2 : -1);
        strat[offset + i][r] = (ord % 2 == 0? -1 : -2);
    }
    ++l, --r;

    int len = (r - l + 1) / a[ord];
    for (int i = 0; i < a[ord]; ++i) {
        for (int x = l + len * i; x <= l + len * (i + 1) - 1; ++x) {
            strat[num][x] = offset + i;
        }

        for (int j = 0; j < a[ord]; ++j) {
            if (i == j) {
                gen(ord + 1, offset + i, l + len * i, l + len * (i + 1) - 1, strat, a);
            } else if (j < i) {
                for (int x = l + len * j; x <= l + len * (j + 1) - 1; ++x) {
                    strat[offset + i][x] = (ord % 2 == 0? -2 : -1);
                }
            } else {
                for (int x = l + len * j; x <= l + len * (j + 1) - 1; ++x) {
                    strat[offset + i][x] = (ord % 2 == 0? -1 : -2);
                }
            }
        }
    }

}

vector<vector<int>> genStrat(vector<int> a) {
    int x = accumulate(a.begin(), a.end(), 0);
    int n = 2;
    for (int i = a.size() - 1; i >= 0; --i) {
        n = n * a[i] + 2;
    }

    //cerr << x << ' ' << n << endl;

    vector<vector<int>> strat(x + 1, vector<int>(n + 1, 0));
    gen(0, 0, 1, n, strat, a);

//    for (auto v : strat) {
//        for (auto x : v) {
//            cerr << setw(2) << x << ' ';
//        }
//        cerr << endl;
//    }

    return strat;
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> res = genStrat({3, 3, 3, 3, 2, 2, 2, 2});
    for (auto &v : res) {
        v.resize(N + 1);
    }
    return res;
}

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