oj.uz

Submission #628895

# Submission time Handle Problem Language Result Execution time Memory
628895 2022-08-13T19:45:17 Z dacin21 Prisoner Challenge (IOI22_prison) C++17
100 / 100
 14 ms 1020 KB 
#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

struct Range{
    int l, r;
};

vector<vector<int>> devise_strategy(int N) {
    const int k = 20;
    vector<vector<int> > ret(k+1, vector<int>(N+1, -1));
    for(auto &e : ret) e[0] = 0;
    auto solve = [&](auto solve, int d, int val, int next_val, Range me, Range other) -> void {
        //cerr << setw(2) << d << " " << setw(2) << val << " : " << me.l << " " << me.r << " / " << other.l << " " << other.r << "\n";
        if(other.l > other.r) return;
        ret[val][0] = d%2;
        const int me_smaller = -1-(d%2);
        const int other_smaller = -1-!(d%2);
        for(int i = me.l; i <= other.l; ++i) ret[val][i] = me_smaller;
        me.l = other.l + 1;
        for(int i = other.r; i <= me.r; ++i) ret[val][i] = other_smaller;
        me.r = other.r - 1;
        if(me.l > me.r) return;

        const int BLOCK = d < 6 ? 3 :  d<7 ? 2 : 1;
        vector<pair<int, Range> > subs(BLOCK);
        for(int i=0; i<BLOCK; ++i){
            subs[i].first = next_val + i;
            subs[i].second.l = me.l + (i*(me.r-me.l+1)+BLOCK-1)/BLOCK;
            subs[i].second.r = me.l + ((i+1)*(me.r-me.l+1)+BLOCK-1)/BLOCK - 1;
            for(int j=subs[i].second.l; j<=subs[i].second.r; ++j){
                ret[val][j] = subs[i].first;
            }
        }
        for(auto &e : subs){
            solve(solve, d+1, e.first, next_val + BLOCK, other, e.second);
        }
    };

    solve(solve, 0, 0, 1, Range{1, N}, Range{1, N});
    return ret;
}

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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 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 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 212 KB Output is correct
4 Correct 1 ms 212 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 1 ms 212 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 0 ms 212 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 11 ms 852 KB Output is correct
6 Correct 14 ms 1020 KB Output is correct
7 Correct 11 ms 948 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 9 ms 844 KB Output is correct