oj.uz

Submission #825596

# Submission time Handle Problem Language Result Execution time Memory
825596 2023-08-15T05:55:03 Z PixelCat Prisoner Challenge (IOI22_prison) C++17
100 / 100
 13 ms 1364 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 13 ms 1364 KB Output is correct
7 Correct 10 ms 1364 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 7 ms 1128 KB Output is correct