Submission #1054329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054329		shiomusubi496	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1136 KiB

prison

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> res(21, vector<int>(N + 1));
    vector<pair<int, int>> v{{1, 5001}};
    int t = (5000 - 2 + 2) / 3;
    {
        res[0][0] = 0;
        rep2 (i, 1, N + 1) {
            if (i == 1) res[0][i] = -1;
            else if (i == 5000) res[0][i] = -2;
            else res[0][i] = 1 + (i - 2) / t;
        }
    }
    rep (i, 6) {
        vector<pair<int, int>> nv;
        int nt = (t - 2 + 2) / 3;
        if (i == 5) nt = (t - 2 + 1) / 2;
        for (auto [l, r] : v) {
            rep (j, 3) {
                res[i * 3 + 1 + j][0] = (i + 1) % 2;
                rep2 (k, l, r) {
                    if (k > N) break;
                    int tmp = 0;
                    if (k == l) tmp = -1 - (i + 1) % 2;
                    else if (k == r - 1) tmp = -1 - i % 2;
                    else if ((k - l - 1) / t < j) tmp = -1 - (i + 1) % 2;
                    else if ((k - l - 1) / t > j) tmp = -1 - i % 2;
                    else if ((k - l - 1) % t == 0) tmp = -1 - (i + 1) % 2;
                    else if ((k - l - 1) % t == t - 1) tmp = -1 - i % 2;
                    else tmp = (i + 1) * 3 + 1 + ((k - l - 1) % t - 1) / nt;
                    res[i * 3 + 1 + j][k] = tmp;
                }
            }
            nv.emplace_back(l + 1, l + 1 + t);
            nv.emplace_back(l + 1 + t, l + 1 + t * 2);
            nv.emplace_back(l + 1 + t * 2, l + 1 + t * 3);
        }
        t = nt;
        v = move(nv);
    }
    for (auto [l, r] : v) {
        int i = 6;
        int nt = 1;
        rep (j, 2) {
            res[i * 3 + 1 + j][0] = (i + 1) % 2;
            rep2 (k, l, r) {
                if (k > N) break;
                int tmp = 0;
                if (k == l) tmp = -1 - (i + 1) % 2;
                else if (k == r - 1) tmp = -1 - i % 2;
                else if ((k - l - 1) / t < j) tmp = -1 - (i + 1) % 2;
                else if ((k - l - 1) / t > j) tmp = -1 - i % 2;
                else if ((k - l - 1) % t == 0) tmp = -1 - (i + 1) % 2;
                else if ((k - l - 1) % t == t - 1) tmp = -1 - i % 2;
                else tmp = (i + 1) * 3 + 1 + ((k - l - 1) % t - 1) / nt;
                res[i * 3 + 1 + j][k] = tmp;
            }
        }
    }
    return res;
}

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