oj.uz

Submission #723248

# Submission time Handle Problem Language Result Execution time Memory
723248 2023-04-13T12:34:06 Z Luicosas Prisoner Challenge (IOI22_prison) C++17
100 / 100
 12 ms 980 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define prv(x) for(auto& pval : x) cout << pval << " "; cout << "\n";
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else 
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> 
ostream& operator << (ostream& out, vector<T> v) {
    for(auto& i : v) {
        out << i << " ";
    }
    return out;
}

std::vector<std::vector<int>> devise_strategy(int n) {
    vector<vector<int>> strat(21, vector<int>(n + 1, 0));
    
    vector<int> lens{3, 3, 3, 3, 3, 2, 2, 1};
    vector<int> idxs{1, 4, 7, 10, 13, 16, 18, 20, 21};
    for(int i = 0; i < sz(lens); i++) {
        assert(idxs[i + 1] == idxs[i] + lens[i]);
    }
    
    // assign lookups
    strat[0][0] = 0;
    for(int i = 0; i < sz(lens); i++) {
        for(int ii = idxs[i]; ii < idxs[i] + lens[i]; ii++) {
            strat[ii][0] = (i ^ 1) & 1;
        }
    }

    // assign connections
    const int a_small = -1, b_small = -2;
    function<void(int,int,int,int)> dfs = [&](int l, int r, int idx, int nlayer) {
        int is_a = (strat[idx][0] == 0);
        if(l >= 0 && l < n + 1) {
            strat[idx][l] = (is_a ? a_small : b_small);
        }
        if(r >= 0 && r < n + 1) {
            strat[idx][r] = (is_a ? b_small : a_small);
        }

        if(l + 1 == r) {
            return;
        }

        int nlen = (r - l - 1) / lens[nlayer]; 
        assert((r - l - 1) % lens[nlayer] == 0);
        for(int i = 0; i < lens[nlayer]; i++) {
            int nl = l + 1 + nlen * i, nr = l + nlen * (i + 1);
            for(int ii = nl; ii <= nr; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idx][ii] = idxs[nlayer] + i;
                }
            }
            for(int ii = l; ii < nl; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idxs[nlayer] + i][ii] = (is_a ? b_small : a_small);
                }
            }
            dfs(nl, nr, idxs[nlayer] + i, nlayer + 1);
            for(int ii = nr + 1; ii <= r; ii++) {
                if(ii >= 0 && ii < n + 1) {
                    strat[idxs[nlayer] + i][ii] = (is_a ? a_small : b_small);
                }
            }
        }
    };
    dfs(1, 5588, 0, 0);

    return strat;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 304 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 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 2 ms 340 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 2 ms 340 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 508 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 11 ms 952 KB Output is correct
7 Correct 12 ms 980 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 5 ms 556 KB Output is correct
12 Correct 8 ms 852 KB Output is correct