Submission #627309

#	Time	Username	Problem	Language	Result	Execution time	Memory
627309		imeimi2000	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	980 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> ans(21, vector<int>(N + 1, 0));
    vector<int> L = { 3, 3, 3, 3, 3, 2, 2, 1, 1 };
    vector<pii> B = { pii(1, N) };
    int board_s = 0, board_e = 0, is_a = 1;
    for (int d : L) {
        vector<pii> C;
        for (int i = board_s; i <= board_e; ++i) {
            ans[i][0] = is_a;
        }
        for (auto [s, e] : B) {
            for (int i = board_s; i <= board_e; ++i) {
                if (ans[i][s] >= 0) ans[i][s] = -1 - is_a;
                if (ans[i][e] >= 0) ans[i][e] = -2 + is_a;
            }
            ++s;
            if (s >= e) continue;
            int c = (e - s + d - 1) / d;
            vector<int> nxt;
            for (int j = s; j < e; j += c) {
                nxt.push_back(j);
            }
            nxt.push_back(e);
            for (int j = 1; j < int(nxt.size()); ++j) {
                int ns = nxt[j - 1], ne = nxt[j] - 1;
                C.emplace_back(ns, ne);
                for (int k = ns; k <= ne; ++k) {
                    for (int i = board_s; i <= board_e; ++i) {
                        if (ans[i][k] >= 0) ans[i][k] = board_e + j;
                    }
                }
                for (int k = s - 1; k < ns; ++k) {
                    ans[board_e + j][k] = -2 + is_a;
                }
                for (int k = ne + 1; k <= e; ++k) {
                    ans[board_e + j][k] = -1 - is_a;
                }
            }
        }
        board_s = board_e + 1;
        board_e += d;
        is_a ^= 1;
        B = C;
    }
    return ans;
}

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