#include "prison.h"

#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
    const std::vector<int> vec = {2, 2, 3, 3, 2, 3, 2, 2, 1};
    // const std::vector<int> vec = {2, 1};

    std::vector<int> vec_sz(vec.size());
    for (int i = vec.size() - 1, c = 2; i >= 0; i--) {
        c = c * vec[i] + 2;
        vec_sz[i] = c;
    }
    assert(vec_sz.front() >= N);

    std::vector<int> prf(vec.size() + 1);
    std::partial_sum(vec.begin(), vec.end(), prf.begin() + 1);

    int x = std::accumulate(vec.begin(), vec.end(), 0);
    std::vector<std::vector<int>> ans(x + 1, std::vector<int>(vec_sz[0] + 1, 0));

    auto fuck = [&](auto fuck, int id, int val, int l, int r, int bag, int l2, int r2) -> void {
        if (l + 1 >= r) {
            assert(false);
        }

        ans[val][0] = !bag;
        for (int i = l2; i <= l; i++) {
            // if (ans[val][i] == -3)
            ans[val][i] = -1 - !bag;
        }
        for (int i = r - 1; i < r2; i++) {
            // if (ans[val][i] == -3)
            ans[val][i] = -1 - bag;
        }
        if (l + 2 == r) {
            return;
        } else {
            l++;
            r--;

            int f = vec[id];
            assert((r - l) % f == 0);
            std::vector<int> fck(f + 1);
            for (int i = 0; i <= f; i++) {
                fck[i] = l + (r - l) / f * i;
            }
            for (int i = 0; i < f; i++) {
                for (int j = fck[i]; j < fck[i + 1]; j++) {
                    ans[val][j] = prf[id] + i + 1;
                }
                fuck(fuck, id + 1, prf[id] + i + 1, fck[i], fck[i + 1], !bag, l - 1, r + 1);
            }
        }
    };
    fuck(fuck, 0, 0, 1, vec_sz.front() + 1, 1, 1, vec_sz.front() + 1);

    for (int i = 0; i <= x; i++) {
        ans[i].resize(N + 1);
    }
    return ans;
}