oj.uz

Submission #565329

# Submission time Handle Problem Language Result Execution time Memory
565329 2022-05-20T17:08:51 Z kartel Fountain Parks (IOI21_parks) C++17
100 / 100
 3143 ms 367740 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "parks.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;

const int N = 2e6 + 500;

mt19937 rnd(time(0));

const int steps[4][2] = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}};
const int dsteps[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

map <pair <int, int>, pair <int, int> > road;

int pr[N];
int cmp[2 * N], to[2 * N];
vector <int> g[2 * N], gr[2 * N], ord;
bool mk[2 * N];

int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int v, int u) {
    v = f(v); u = f(u);
    if (v == u) {
        return;
    }
    pr[u] = v;
}

int nt(int x) {return (x < N ? x + N : x - N);}

void add_impl(int a, int b) {
    int na = nt(a), nb = nt(b);

    g[na].pb(b); gr[b].pb(na);
    g[nb].pb(a); gr[a].pb(nb);
}

void dfs(int v) {
    mk[v] = 1;
    for (auto u : g[v]) {
        if (mk[u]) {
            continue;
        }
        dfs(u);
    }
    ord.pb(v);
}

void get_erased_2x2(const vector <int> &x, const vector <int> &y, map<pair <int, int>, int> &del) {
    map <pair <int, int>, int> cnt, who;
    vector <pair <int, int> > pts;

    for (int i = 0; i < sz(x); i++) {
        who[{x[i], y[i]}] = i;
        for (int j = 0; j < 4; j++) {
            int cx = x[i] + dsteps[j][0];
            int cy = y[i] + dsteps[j][1];

            cnt[{cx, cy}]++;
            if (cnt[{cx, cy}] == 4) {
                pts.pb({cx, cy});
            }
        }
    }
    sort(all(pts));
    vector <vector <int> > g(sz(pts));
    cnt.clear();
    int ptr = 0;
    for (auto &[x, y] : pts) {
        cnt[{x, y}] = ptr++;
    }

    ptr = 0;
    for (auto &[x, y] : pts) {
        int par = (x / 2 + y / 2) % 2;
        for (int i = 0; i < 2; i++) {
            int cx = x + steps[i * 2 + par][0];
            int cy = y + steps[i * 2 + par][1];

            if (!cnt.count({cx, cy})) {
                continue;
            }
            g[cnt[{cx, cy}]].pb(ptr);
        }
        ptr++;
    }

    vector <pair <int, int> > block(sz(pts));
    vector <int> mk(sz(pts), 0);
    for (int i = 0; i < sz(pts); i++) {
        if (mk[i]) {
            continue;
        }
        function <void(int)> dfs = [&](int v) {
            mk[v] = 1;
            for (auto u : g[v]) {
                if (mk[u]) {
                    continue;
                }
                dfs(u);
                int dx = pts[v].F - pts[u].F;
                int dy = pts[v].S - pts[u].S;
                block[u] = road[{dx, dy}];
            }
        };

        int par = (pts[i].F / 2 + pts[i].S / 2) & 1;
        if (par & 1) {
            block[i] = road[{-2, 0}];
        } else {
            block[i] = road[{0, -2}];
        }
        dfs(i);
    }

    for (int i = 0; i < sz(pts); i++) {
        auto [x, y] = pts[i];

        auto [a, b] = block[i];
        int v = who[{x + dsteps[a][0], y + dsteps[a][1]}];
        int u = who[{x + dsteps[b][0], y + dsteps[b][1]}];

        del[{v, u}] = del[{u, v}] = 1;
    }
}

/*

5
4 4
4 6
6 4
4 2
2 4

*/

int construct_roads(vector <int> x, vector <int> y) {
    int n = sz(x);

    road[{0, 2}]  = {2, 0}; road[{2, 0}]  = {0, 1};
    road[{0, -2}] = {1, 3}; road[{-2, 0}] = {3, 2};

    map <pair <int, int>, int> mp;
    vector <pair <int, int> > r;
    map <pair <int, int>, int> del;
    vector <int> pm(n);
    iota(all(pm), 0);
    shuffle(all(pm), rnd);

    bool sd = 1;
    for (int i = 0; i < n; i++) {
        mp[{x[i], y[i]}] = i;
        pr[i] = i;
        sd &= (x[i] >= 2 && x[i] <= 4);
    }

    get_erased_2x2(x, y, del);
    for (auto i : pm) {
        for (int j = 0; j < 4; j++) {
            int cx = x[i] + steps[j][0];
            int cy = y[i] + steps[j][1];

            if (mp.count({cx, cy}) && f(i) != f(mp[{cx, cy}])) {
                int to = mp[{cx, cy}];
                if (del[{i, to}]) {
                    continue;
                }
                link(i, to);
                r.pb({i, to});
            }
        }
    }
    sort(all(r));
    r.resize(unique(all(r)) - r.begin());

    for (int i = 0; i < n; i++) {
        if (f(i) != f(0)) {
            return 0;
        }
    }
    vector <int> u, v, A, B;
    map <pair <int, int>, vector <int> > e;


    for (int i = 0; i < sz(r); i++) {
        int a = r[i].F, b = r[i].S;
        u.pb(a); v.pb(b);
        if (abs(x[a] - x[b]) == 0) {
            int lx = x[a];
            int ly = min(y[a], y[b]);

            e[{lx - 1, ly + 1}].pb(i);
            e[{lx + 1, ly + 1}].pb(nt(i));
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            e[{lx + 1, ly + 1}].pb(i);
            e[{lx + 1, ly - 1}].pb(nt(i));
        }
    }
    for (auto [p, v] : e) {
        int x = p.F, y = p.S;
        if (sz(v) == 1) {
            continue;
        }
        for (auto a : v) {
            for (auto b : v) {
                if (a == b) {
                    continue;
                }
                add_impl(a, b);
            }
        }
    }

    for (int i = 0; i < 2 * N; i++) {
        cmp[i] = -1;
        if (mk[i]) {
            continue;
        }
        dfs(i);
    }
    reverse(all(ord));

    int C = 0;
    for (auto v : ord) {
        function <void(int)> dfsr = [&](int v) {
            if (cmp[v] != -1) {
                return;
            }
            cmp[v] = C;
            for (auto u : gr[v]) {
                dfsr(u);
            }
        };

        dfsr(v);
        C++;
    }

    for (int i = 0; i < N; i++) {
        if (cmp[i] == cmp[nt(i)]) {
            return 0;
        }
        to[i] = (cmp[i] > cmp[nt(i)]);
    }

    for (int i = 0; i < sz(r); i++) {
        int a = r[i].F, b = r[i].S;
        if (abs(x[a] - x[b]) == 0) {
            int lx = x[a];
            int ly = min(y[a], y[b]);

            if (to[i]) {
                A.pb(lx + 1);
            } else {
                A.pb(lx - 1);
            }
            B.pb(ly + 1);
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            if (to[i]) {
                B.pb(ly - 1);
            } else {
                B.pb(ly + 1);
            }
            A.pb(lx + 1);
        }
    }

    build(u, v, A, B);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:216:13: warning: unused variable 'x' [-Wunused-variable]
  216 |         int x = p.F, y = p.S;
      |             ^
parks.cpp:216:22: warning: unused variable 'y' [-Wunused-variable]
  216 |         int x = p.F, y = p.S;
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct
17 Correct 174 ms 231420 KB Output is correct
18 Correct 194 ms 231308 KB Output is correct
19 Correct 167 ms 231320 KB Output is correct
20 Correct 185 ms 231432 KB Output is correct
21 Correct 113 ms 188168 KB Output is correct
22 Correct 177 ms 231300 KB Output is correct
23 Correct 3000 ms 331916 KB Output is correct
24 Correct 173 ms 231400 KB Output is correct
25 Correct 174 ms 231872 KB Output is correct
26 Correct 106 ms 189004 KB Output is correct
27 Correct 104 ms 189332 KB Output is correct
28 Correct 1031 ms 270872 KB Output is correct
29 Correct 1652 ms 291628 KB Output is correct
30 Correct 2247 ms 310056 KB Output is correct
31 Correct 2991 ms 332024 KB Output is correct
32 Correct 160 ms 231364 KB Output is correct
33 Correct 161 ms 231328 KB Output is correct
34 Correct 162 ms 231312 KB Output is correct
35 Correct 103 ms 188216 KB Output is correct
36 Correct 127 ms 188220 KB Output is correct
37 Correct 174 ms 231424 KB Output is correct
38 Correct 171 ms 231404 KB Output is correct
39 Correct 168 ms 231400 KB Output is correct
40 Correct 167 ms 231312 KB Output is correct
41 Correct 100 ms 188228 KB Output is correct
42 Correct 185 ms 231436 KB Output is correct
43 Correct 105 ms 188744 KB Output is correct
44 Correct 120 ms 189064 KB Output is correct
45 Correct 1134 ms 275828 KB Output is correct
46 Correct 1647 ms 295336 KB Output is correct
47 Correct 1637 ms 295936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct
17 Correct 174 ms 231420 KB Output is correct
18 Correct 194 ms 231308 KB Output is correct
19 Correct 167 ms 231320 KB Output is correct
20 Correct 185 ms 231432 KB Output is correct
21 Correct 113 ms 188168 KB Output is correct
22 Correct 177 ms 231300 KB Output is correct
23 Correct 3000 ms 331916 KB Output is correct
24 Correct 173 ms 231400 KB Output is correct
25 Correct 174 ms 231872 KB Output is correct
26 Correct 106 ms 189004 KB Output is correct
27 Correct 104 ms 189332 KB Output is correct
28 Correct 1031 ms 270872 KB Output is correct
29 Correct 1652 ms 291628 KB Output is correct
30 Correct 2247 ms 310056 KB Output is correct
31 Correct 2991 ms 332024 KB Output is correct
32 Correct 160 ms 231364 KB Output is correct
33 Correct 161 ms 231328 KB Output is correct
34 Correct 162 ms 231312 KB Output is correct
35 Correct 103 ms 188216 KB Output is correct
36 Correct 127 ms 188220 KB Output is correct
37 Correct 174 ms 231424 KB Output is correct
38 Correct 171 ms 231404 KB Output is correct
39 Correct 168 ms 231400 KB Output is correct
40 Correct 167 ms 231312 KB Output is correct
41 Correct 100 ms 188228 KB Output is correct
42 Correct 185 ms 231436 KB Output is correct
43 Correct 105 ms 188744 KB Output is correct
44 Correct 120 ms 189064 KB Output is correct
45 Correct 1134 ms 275828 KB Output is correct
46 Correct 1647 ms 295336 KB Output is correct
47 Correct 1637 ms 295936 KB Output is correct
48 Correct 173 ms 231312 KB Output is correct
49 Correct 176 ms 231312 KB Output is correct
50 Correct 186 ms 231344 KB Output is correct
51 Correct 181 ms 231340 KB Output is correct
52 Correct 171 ms 231400 KB Output is correct
53 Correct 176 ms 231384 KB Output is correct
54 Correct 189 ms 231404 KB Output is correct
55 Correct 3143 ms 351464 KB Output is correct
56 Correct 205 ms 231420 KB Output is correct
57 Correct 184 ms 232364 KB Output is correct
58 Correct 214 ms 234936 KB Output is correct
59 Correct 147 ms 191600 KB Output is correct
60 Correct 1406 ms 291080 KB Output is correct
61 Correct 1955 ms 312620 KB Output is correct
62 Correct 2416 ms 330864 KB Output is correct
63 Correct 2988 ms 351932 KB Output is correct
64 Correct 106 ms 188168 KB Output is correct
65 Correct 165 ms 231344 KB Output is correct
66 Correct 99 ms 188112 KB Output is correct
67 Correct 2061 ms 318916 KB Output is correct
68 Correct 2029 ms 318952 KB Output is correct
69 Correct 2043 ms 318524 KB Output is correct
70 Correct 125 ms 189220 KB Output is correct
71 Correct 124 ms 190432 KB Output is correct
72 Correct 973 ms 275840 KB Output is correct
73 Correct 1543 ms 298896 KB Output is correct
74 Correct 2131 ms 320884 KB Output is correct
75 Correct 2059 ms 320944 KB Output is correct
76 Correct 1899 ms 318912 KB Output is correct
77 Correct 114 ms 189452 KB Output is correct
78 Correct 123 ms 190644 KB Output is correct
79 Correct 937 ms 275884 KB Output is correct
80 Correct 1575 ms 299384 KB Output is correct
81 Correct 2118 ms 321380 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct
17 Correct 173 ms 231312 KB Output is correct
18 Correct 163 ms 231300 KB Output is correct
19 Correct 101 ms 188156 KB Output is correct
20 Correct 1999 ms 326792 KB Output is correct
21 Correct 2147 ms 325024 KB Output is correct
22 Correct 2119 ms 324848 KB Output is correct
23 Correct 1502 ms 305108 KB Output is correct
24 Correct 1185 ms 268048 KB Output is correct
25 Correct 1649 ms 243136 KB Output is correct
26 Correct 1438 ms 243168 KB Output is correct
27 Correct 1881 ms 316364 KB Output is correct
28 Correct 1860 ms 317176 KB Output is correct
29 Correct 2075 ms 317184 KB Output is correct
30 Correct 2025 ms 317396 KB Output is correct
31 Correct 166 ms 231384 KB Output is correct
32 Correct 240 ms 237676 KB Output is correct
33 Correct 498 ms 221796 KB Output is correct
34 Correct 1947 ms 325488 KB Output is correct
35 Correct 138 ms 190676 KB Output is correct
36 Correct 331 ms 201428 KB Output is correct
37 Correct 682 ms 213812 KB Output is correct
38 Correct 819 ms 267224 KB Output is correct
39 Correct 1073 ms 280412 KB Output is correct
40 Correct 1434 ms 293100 KB Output is correct
41 Correct 1818 ms 307532 KB Output is correct
42 Correct 2177 ms 320872 KB Output is correct
43 Correct 164 ms 231400 KB Output is correct
44 Correct 171 ms 231424 KB Output is correct
45 Correct 164 ms 231412 KB Output is correct
46 Correct 99 ms 188124 KB Output is correct
47 Correct 105 ms 188284 KB Output is correct
48 Correct 165 ms 231380 KB Output is correct
49 Correct 164 ms 231364 KB Output is correct
50 Correct 167 ms 231312 KB Output is correct
51 Correct 165 ms 231304 KB Output is correct
52 Correct 99 ms 188120 KB Output is correct
53 Correct 165 ms 231396 KB Output is correct
54 Correct 105 ms 188640 KB Output is correct
55 Correct 111 ms 188928 KB Output is correct
56 Correct 947 ms 274808 KB Output is correct
57 Correct 1458 ms 294356 KB Output is correct
58 Correct 1393 ms 294040 KB Output is correct
59 Correct 103 ms 188124 KB Output is correct
60 Correct 176 ms 231392 KB Output is correct
61 Correct 103 ms 188148 KB Output is correct
62 Correct 1845 ms 317492 KB Output is correct
63 Correct 1775 ms 317260 KB Output is correct
64 Correct 1798 ms 316808 KB Output is correct
65 Correct 110 ms 189224 KB Output is correct
66 Correct 125 ms 190376 KB Output is correct
67 Correct 917 ms 275184 KB Output is correct
68 Correct 1515 ms 297840 KB Output is correct
69 Correct 2110 ms 319292 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct
17 Correct 1993 ms 317660 KB Output is correct
18 Correct 2001 ms 318196 KB Output is correct
19 Correct 2325 ms 326236 KB Output is correct
20 Correct 2124 ms 317892 KB Output is correct
21 Correct 1753 ms 306508 KB Output is correct
22 Correct 159 ms 231424 KB Output is correct
23 Correct 323 ms 245532 KB Output is correct
24 Correct 163 ms 193228 KB Output is correct
25 Correct 432 ms 205204 KB Output is correct
26 Correct 791 ms 217360 KB Output is correct
27 Correct 945 ms 275552 KB Output is correct
28 Correct 1201 ms 287164 KB Output is correct
29 Correct 1558 ms 298940 KB Output is correct
30 Correct 1811 ms 307928 KB Output is correct
31 Correct 2084 ms 320572 KB Output is correct
32 Correct 2009 ms 318992 KB Output is correct
33 Correct 1761 ms 317336 KB Output is correct
34 Correct 108 ms 189408 KB Output is correct
35 Correct 123 ms 190556 KB Output is correct
36 Correct 910 ms 275124 KB Output is correct
37 Correct 1581 ms 297980 KB Output is correct
38 Correct 1990 ms 319080 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 231348 KB Output is correct
2 Correct 165 ms 231308 KB Output is correct
3 Correct 97 ms 188184 KB Output is correct
4 Correct 164 ms 231404 KB Output is correct
5 Correct 186 ms 231508 KB Output is correct
6 Correct 102 ms 188200 KB Output is correct
7 Correct 105 ms 188172 KB Output is correct
8 Correct 103 ms 188108 KB Output is correct
9 Correct 942 ms 274288 KB Output is correct
10 Correct 213 ms 235664 KB Output is correct
11 Correct 462 ms 254300 KB Output is correct
12 Correct 228 ms 237940 KB Output is correct
13 Correct 267 ms 200348 KB Output is correct
14 Correct 100 ms 188472 KB Output is correct
15 Correct 98 ms 188692 KB Output is correct
16 Correct 969 ms 274280 KB Output is correct
17 Correct 174 ms 231420 KB Output is correct
18 Correct 194 ms 231308 KB Output is correct
19 Correct 167 ms 231320 KB Output is correct
20 Correct 185 ms 231432 KB Output is correct
21 Correct 113 ms 188168 KB Output is correct
22 Correct 177 ms 231300 KB Output is correct
23 Correct 3000 ms 331916 KB Output is correct
24 Correct 173 ms 231400 KB Output is correct
25 Correct 174 ms 231872 KB Output is correct
26 Correct 106 ms 189004 KB Output is correct
27 Correct 104 ms 189332 KB Output is correct
28 Correct 1031 ms 270872 KB Output is correct
29 Correct 1652 ms 291628 KB Output is correct
30 Correct 2247 ms 310056 KB Output is correct
31 Correct 2991 ms 332024 KB Output is correct
32 Correct 160 ms 231364 KB Output is correct
33 Correct 161 ms 231328 KB Output is correct
34 Correct 162 ms 231312 KB Output is correct
35 Correct 103 ms 188216 KB Output is correct
36 Correct 127 ms 188220 KB Output is correct
37 Correct 174 ms 231424 KB Output is correct
38 Correct 171 ms 231404 KB Output is correct
39 Correct 168 ms 231400 KB Output is correct
40 Correct 167 ms 231312 KB Output is correct
41 Correct 100 ms 188228 KB Output is correct
42 Correct 185 ms 231436 KB Output is correct
43 Correct 105 ms 188744 KB Output is correct
44 Correct 120 ms 189064 KB Output is correct
45 Correct 1134 ms 275828 KB Output is correct
46 Correct 1647 ms 295336 KB Output is correct
47 Correct 1637 ms 295936 KB Output is correct
48 Correct 173 ms 231312 KB Output is correct
49 Correct 176 ms 231312 KB Output is correct
50 Correct 186 ms 231344 KB Output is correct
51 Correct 181 ms 231340 KB Output is correct
52 Correct 171 ms 231400 KB Output is correct
53 Correct 176 ms 231384 KB Output is correct
54 Correct 189 ms 231404 KB Output is correct
55 Correct 3143 ms 351464 KB Output is correct
56 Correct 205 ms 231420 KB Output is correct
57 Correct 184 ms 232364 KB Output is correct
58 Correct 214 ms 234936 KB Output is correct
59 Correct 147 ms 191600 KB Output is correct
60 Correct 1406 ms 291080 KB Output is correct
61 Correct 1955 ms 312620 KB Output is correct
62 Correct 2416 ms 330864 KB Output is correct
63 Correct 2988 ms 351932 KB Output is correct
64 Correct 106 ms 188168 KB Output is correct
65 Correct 165 ms 231344 KB Output is correct
66 Correct 99 ms 188112 KB Output is correct
67 Correct 2061 ms 318916 KB Output is correct
68 Correct 2029 ms 318952 KB Output is correct
69 Correct 2043 ms 318524 KB Output is correct
70 Correct 125 ms 189220 KB Output is correct
71 Correct 124 ms 190432 KB Output is correct
72 Correct 973 ms 275840 KB Output is correct
73 Correct 1543 ms 298896 KB Output is correct
74 Correct 2131 ms 320884 KB Output is correct
75 Correct 2059 ms 320944 KB Output is correct
76 Correct 1899 ms 318912 KB Output is correct
77 Correct 114 ms 189452 KB Output is correct
78 Correct 123 ms 190644 KB Output is correct
79 Correct 937 ms 275884 KB Output is correct
80 Correct 1575 ms 299384 KB Output is correct
81 Correct 2118 ms 321380 KB Output is correct
82 Correct 173 ms 231312 KB Output is correct
83 Correct 163 ms 231300 KB Output is correct
84 Correct 101 ms 188156 KB Output is correct
85 Correct 1999 ms 326792 KB Output is correct
86 Correct 2147 ms 325024 KB Output is correct
87 Correct 2119 ms 324848 KB Output is correct
88 Correct 1502 ms 305108 KB Output is correct
89 Correct 1185 ms 268048 KB Output is correct
90 Correct 1649 ms 243136 KB Output is correct
91 Correct 1438 ms 243168 KB Output is correct
92 Correct 1881 ms 316364 KB Output is correct
93 Correct 1860 ms 317176 KB Output is correct
94 Correct 2075 ms 317184 KB Output is correct
95 Correct 2025 ms 317396 KB Output is correct
96 Correct 166 ms 231384 KB Output is correct
97 Correct 240 ms 237676 KB Output is correct
98 Correct 498 ms 221796 KB Output is correct
99 Correct 1947 ms 325488 KB Output is correct
100 Correct 138 ms 190676 KB Output is correct
101 Correct 331 ms 201428 KB Output is correct
102 Correct 682 ms 213812 KB Output is correct
103 Correct 819 ms 267224 KB Output is correct
104 Correct 1073 ms 280412 KB Output is correct
105 Correct 1434 ms 293100 KB Output is correct
106 Correct 1818 ms 307532 KB Output is correct
107 Correct 2177 ms 320872 KB Output is correct
108 Correct 164 ms 231400 KB Output is correct
109 Correct 171 ms 231424 KB Output is correct
110 Correct 164 ms 231412 KB Output is correct
111 Correct 99 ms 188124 KB Output is correct
112 Correct 105 ms 188284 KB Output is correct
113 Correct 165 ms 231380 KB Output is correct
114 Correct 164 ms 231364 KB Output is correct
115 Correct 167 ms 231312 KB Output is correct
116 Correct 165 ms 231304 KB Output is correct
117 Correct 99 ms 188120 KB Output is correct
118 Correct 165 ms 231396 KB Output is correct
119 Correct 105 ms 188640 KB Output is correct
120 Correct 111 ms 188928 KB Output is correct
121 Correct 947 ms 274808 KB Output is correct
122 Correct 1458 ms 294356 KB Output is correct
123 Correct 1393 ms 294040 KB Output is correct
124 Correct 103 ms 188124 KB Output is correct
125 Correct 176 ms 231392 KB Output is correct
126 Correct 103 ms 188148 KB Output is correct
127 Correct 1845 ms 317492 KB Output is correct
128 Correct 1775 ms 317260 KB Output is correct
129 Correct 1798 ms 316808 KB Output is correct
130 Correct 110 ms 189224 KB Output is correct
131 Correct 125 ms 190376 KB Output is correct
132 Correct 917 ms 275184 KB Output is correct
133 Correct 1515 ms 297840 KB Output is correct
134 Correct 2110 ms 319292 KB Output is correct
135 Correct 1993 ms 317660 KB Output is correct
136 Correct 2001 ms 318196 KB Output is correct
137 Correct 2325 ms 326236 KB Output is correct
138 Correct 2124 ms 317892 KB Output is correct
139 Correct 1753 ms 306508 KB Output is correct
140 Correct 159 ms 231424 KB Output is correct
141 Correct 323 ms 245532 KB Output is correct
142 Correct 163 ms 193228 KB Output is correct
143 Correct 432 ms 205204 KB Output is correct
144 Correct 791 ms 217360 KB Output is correct
145 Correct 945 ms 275552 KB Output is correct
146 Correct 1201 ms 287164 KB Output is correct
147 Correct 1558 ms 298940 KB Output is correct
148 Correct 1811 ms 307928 KB Output is correct
149 Correct 2084 ms 320572 KB Output is correct
150 Correct 2009 ms 318992 KB Output is correct
151 Correct 1761 ms 317336 KB Output is correct
152 Correct 108 ms 189408 KB Output is correct
153 Correct 123 ms 190556 KB Output is correct
154 Correct 910 ms 275124 KB Output is correct
155 Correct 1581 ms 297980 KB Output is correct
156 Correct 1990 ms 319080 KB Output is correct
157 Correct 159 ms 231540 KB Output is correct
158 Correct 95 ms 188116 KB Output is correct
159 Correct 156 ms 231380 KB Output is correct
160 Correct 159 ms 231372 KB Output is correct
161 Correct 2985 ms 367740 KB Output is correct
162 Correct 1881 ms 330220 KB Output is correct
163 Correct 2192 ms 329488 KB Output is correct
164 Correct 2214 ms 329500 KB Output is correct
165 Correct 2646 ms 351748 KB Output is correct
166 Correct 2804 ms 356544 KB Output is correct
167 Correct 544 ms 257080 KB Output is correct
168 Correct 266 ms 201416 KB Output is correct
169 Correct 722 ms 221288 KB Output is correct
170 Correct 1486 ms 249840 KB Output is correct
171 Correct 2160 ms 268600 KB Output is correct
172 Correct 1266 ms 295588 KB Output is correct
173 Correct 1549 ms 308048 KB Output is correct
174 Correct 2029 ms 322472 KB Output is correct
175 Correct 2230 ms 334276 KB Output is correct
176 Correct 2588 ms 347832 KB Output is correct
177 Correct 2942 ms 361252 KB Output is correct