Submission #628895

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
628895	2022-08-13 19:45:17	dacin21	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	1020 KiB

prison

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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