Submission #825596

#	Time	Username	Problem	Language	Result	Execution time	Memory
825596		PixelCat	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1364 KiB

prison

#include "prison.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

struct Ayaya { int al, ar, bl, br; };

vector<int> blk;
vector<vector<int>> res;

vector<vector<int>> devise_strategy(int N) {
    blk.eb(0);
    For(i, 1, 4) blk.eb(3);
    For(i, 1, 20) blk.eb(2);

    int dep = 0;
    vector<vector<Ayaya>> ayaya(1);
    ayaya[0].push_back({1, N, 1, N});
    while(sz(ayaya)) {
        dep++;
        int k = blk[dep];
        int s2 = sz(res) + sz(ayaya);
        vector<vector<Ayaya>> ay2(k);
        for(auto &aya:ayaya) {
            res.eb(N + 1, -1);
            res.back()[0] = dep % 2;
            for(auto &it:aya) {
                vector<pii> owo;
                int l = it.bl + 1, r = it.br - 1;
                // cerr << dep << " " << l << " " << r << " " << it.al << " " << it.ar << "\n";

                if(k == 2) {
                    int m = l + ((r - l + 2) / 2) - 1;
                    owo.eb(l, m);
                    owo.eb(m + 1, r);
                } else if(k == 3) {
                    int m1 = l + ((r - l + 3) / 3) - 1;
                    int m2 = l + ((r - l + 3) / 3) * 2 - 1;
                    owo.eb(l, m1);
                    owo.eb(m1 + 1, m2);
                    owo.eb(m2 + 1, r);
                }
                int cnt = 0;
                For(ow, 0, k - 1) {
                    auto p = owo[ow];
                    if(p.F <= p.S) {
                        For(i, p.F, p.S) res.back()[i] = s2 + cnt;
                        ay2[cnt].push_back({it.bl, it.br, p.F, p.S});
                        cnt++;
                    }
                }

                For(i, it.al, l - 1) res.back()[i] = -1 - dep % 2;
                For(i, r + 1, it.ar) res.back()[i] = -2 + dep % 2;
            }
        }

        while(sz(ay2) && sz(ay2.back()) == 0) ay2.pop_back();
        ayaya = ay2;
    }

#ifdef NYAOWO
    cerr << "x = " << (sz(res) - 1) << "\n";
    For(i, 0, sz(res) - 1) {
        cerr << "(" << res[i][0] << ")";
        For(j, 1, N) cerr << " " << res[i][j];
        cerr << "\n";
    }
#endif

    return res;
}

/*

3
1 2
1 3
2 1
2 3
3 1
3 2
-1

A
A
B
A
B
B

*/

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