oj.uz

Submission #566545

# Submission time Handle Problem Language Result Execution time Memory
566545 2022-05-22T11:41:41 Z kartel Fountain Parks (IOI21_parks) C++17
100 / 100
 3078 ms 178072 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "ext/pb_ds/assoc_container.hpp"
#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;
using namespace __gnu_pbds;
typedef long long ll;

const int N = 5e5 + 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}};

pair <int, int> road[10][10];

pair <int, int> block[N * 2];
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);
}
vector <pair <int, int> > pts;

void dfsd(int v) {
    mk[v] = 1;
    for (auto &u : g[v]) {
        if (mk[u]) {
            continue;
        }
        int dx = pts[v].F - pts[u].F;
        int dy = pts[v].S - pts[u].S;
        block[u] = road[dx + 4][dy + 4];
        dfsd(u);
    }
}

inline ll geth(int a, int b) {return ((ll)a << 20) + b;}

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

    for (int i = 0; i < sz(x); i++) {
        who[geth(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[geth(cx, cy)]++;
            if (cnt[geth(cx, cy)] == 4) {
                pts.pb({cx, cy});
            }
        }
    }
    sort(all(pts));
    cnt.clear();
    int ptr = 0;
    for (auto &[x, y] : pts) {
        cnt[geth(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.find(geth(cx, cy)) == cnt.end()) {
                continue;
            }
            g[cnt[geth(cx, cy)]].pb(ptr);
        }
        ptr++;
    }

    queue <int> q;
    for (int i = 0; i < sz(pts); i++) {
        if (mk[i]) {
            continue;
        }

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

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

        auto &[a, b] = block[i];
        int v = who[geth(x + dsteps[a][0], y + dsteps[a][1])];
        int u = who[geth(x + dsteps[b][0], y + dsteps[b][1])];

        del[geth(v, u)] = del[geth(u, v)] = 1;
    }
}

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

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

    map <ll, int> mp;
    vector <pair <int, int> > r;
    map <ll, 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[geth(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.find(geth(cx, cy)) != mp.end() && f(i) != f(mp[geth(cx, cy)])) {
                int to = mp[geth(cx, cy)];
                if (del.find(geth(i, to)) != del.end()) {
                    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 <ll, 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[geth(lx - 1, ly + 1)].pb(i);
            e[geth(lx + 1, ly + 1)].pb(nt(i));
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            e[geth(lx + 1, ly + 1)].pb(i);
            e[geth(lx + 1, ly - 1)].pb(nt(i));
        }
    }
    for (int i = 0; i < 2 * N; i++) {
        mk[i] = 0;
        g[i].clear();
    }
    for (auto &[p, v] : e) {
        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct
17 Correct 42 ms 58168 KB Output is correct
18 Correct 43 ms 58224 KB Output is correct
19 Correct 42 ms 58156 KB Output is correct
20 Correct 49 ms 58128 KB Output is correct
21 Correct 27 ms 47248 KB Output is correct
22 Correct 47 ms 58220 KB Output is correct
23 Correct 2321 ms 145892 KB Output is correct
24 Correct 46 ms 58172 KB Output is correct
25 Correct 48 ms 58684 KB Output is correct
26 Correct 33 ms 48124 KB Output is correct
27 Correct 36 ms 48432 KB Output is correct
28 Correct 761 ms 93092 KB Output is correct
29 Correct 1248 ms 110488 KB Output is correct
30 Correct 1802 ms 128420 KB Output is correct
31 Correct 2387 ms 145628 KB Output is correct
32 Correct 40 ms 58140 KB Output is correct
33 Correct 41 ms 58192 KB Output is correct
34 Correct 43 ms 58236 KB Output is correct
35 Correct 24 ms 47220 KB Output is correct
36 Correct 27 ms 47212 KB Output is correct
37 Correct 42 ms 58216 KB Output is correct
38 Correct 41 ms 58128 KB Output is correct
39 Correct 42 ms 58196 KB Output is correct
40 Correct 42 ms 58144 KB Output is correct
41 Correct 25 ms 47296 KB Output is correct
42 Correct 40 ms 58168 KB Output is correct
43 Correct 27 ms 47828 KB Output is correct
44 Correct 32 ms 48084 KB Output is correct
45 Correct 717 ms 96744 KB Output is correct
46 Correct 1186 ms 115828 KB Output is correct
47 Correct 1227 ms 115052 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct
17 Correct 42 ms 58168 KB Output is correct
18 Correct 43 ms 58224 KB Output is correct
19 Correct 42 ms 58156 KB Output is correct
20 Correct 49 ms 58128 KB Output is correct
21 Correct 27 ms 47248 KB Output is correct
22 Correct 47 ms 58220 KB Output is correct
23 Correct 2321 ms 145892 KB Output is correct
24 Correct 46 ms 58172 KB Output is correct
25 Correct 48 ms 58684 KB Output is correct
26 Correct 33 ms 48124 KB Output is correct
27 Correct 36 ms 48432 KB Output is correct
28 Correct 761 ms 93092 KB Output is correct
29 Correct 1248 ms 110488 KB Output is correct
30 Correct 1802 ms 128420 KB Output is correct
31 Correct 2387 ms 145628 KB Output is correct
32 Correct 40 ms 58140 KB Output is correct
33 Correct 41 ms 58192 KB Output is correct
34 Correct 43 ms 58236 KB Output is correct
35 Correct 24 ms 47220 KB Output is correct
36 Correct 27 ms 47212 KB Output is correct
37 Correct 42 ms 58216 KB Output is correct
38 Correct 41 ms 58128 KB Output is correct
39 Correct 42 ms 58196 KB Output is correct
40 Correct 42 ms 58144 KB Output is correct
41 Correct 25 ms 47296 KB Output is correct
42 Correct 40 ms 58168 KB Output is correct
43 Correct 27 ms 47828 KB Output is correct
44 Correct 32 ms 48084 KB Output is correct
45 Correct 717 ms 96744 KB Output is correct
46 Correct 1186 ms 115828 KB Output is correct
47 Correct 1227 ms 115052 KB Output is correct
48 Correct 40 ms 58168 KB Output is correct
49 Correct 40 ms 58216 KB Output is correct
50 Correct 43 ms 58136 KB Output is correct
51 Correct 43 ms 58216 KB Output is correct
52 Correct 44 ms 58168 KB Output is correct
53 Correct 45 ms 58148 KB Output is correct
54 Correct 42 ms 58244 KB Output is correct
55 Correct 2651 ms 163588 KB Output is correct
56 Correct 42 ms 58168 KB Output is correct
57 Correct 51 ms 59056 KB Output is correct
58 Correct 71 ms 61284 KB Output is correct
59 Correct 64 ms 50620 KB Output is correct
60 Correct 1077 ms 111172 KB Output is correct
61 Correct 1621 ms 129508 KB Output is correct
62 Correct 2032 ms 145100 KB Output is correct
63 Correct 2596 ms 164192 KB Output is correct
64 Correct 23 ms 47316 KB Output is correct
65 Correct 40 ms 58200 KB Output is correct
66 Correct 22 ms 47292 KB Output is correct
67 Correct 1694 ms 133604 KB Output is correct
68 Correct 1683 ms 133568 KB Output is correct
69 Correct 1829 ms 133232 KB Output is correct
70 Correct 41 ms 48284 KB Output is correct
71 Correct 49 ms 49404 KB Output is correct
72 Correct 991 ms 96660 KB Output is correct
73 Correct 1745 ms 117440 KB Output is correct
74 Correct 2493 ms 135444 KB Output is correct
75 Correct 2346 ms 135696 KB Output is correct
76 Correct 1985 ms 133560 KB Output is correct
77 Correct 53 ms 48500 KB Output is correct
78 Correct 53 ms 49540 KB Output is correct
79 Correct 954 ms 96892 KB Output is correct
80 Correct 1663 ms 117504 KB Output is correct
81 Correct 2422 ms 135200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct
17 Correct 46 ms 58140 KB Output is correct
18 Correct 51 ms 58200 KB Output is correct
19 Correct 27 ms 47320 KB Output is correct
20 Correct 2059 ms 143244 KB Output is correct
21 Correct 2029 ms 139436 KB Output is correct
22 Correct 2009 ms 139108 KB Output is correct
23 Correct 1418 ms 121108 KB Output is correct
24 Correct 1238 ms 127180 KB Output is correct
25 Correct 1490 ms 102264 KB Output is correct
26 Correct 1349 ms 102080 KB Output is correct
27 Correct 1849 ms 133584 KB Output is correct
28 Correct 1786 ms 133548 KB Output is correct
29 Correct 1938 ms 133476 KB Output is correct
30 Correct 1989 ms 133544 KB Output is correct
31 Correct 41 ms 58168 KB Output is correct
32 Correct 118 ms 63744 KB Output is correct
33 Correct 477 ms 81116 KB Output is correct
34 Correct 1858 ms 141812 KB Output is correct
35 Correct 51 ms 49876 KB Output is correct
36 Correct 259 ms 60176 KB Output is correct
37 Correct 572 ms 72848 KB Output is correct
38 Correct 666 ms 89992 KB Output is correct
39 Correct 971 ms 101156 KB Output is correct
40 Correct 1359 ms 114412 KB Output is correct
41 Correct 1815 ms 126008 KB Output is correct
42 Correct 2118 ms 136552 KB Output is correct
43 Correct 42 ms 58168 KB Output is correct
44 Correct 48 ms 58128 KB Output is correct
45 Correct 47 ms 58208 KB Output is correct
46 Correct 25 ms 47336 KB Output is correct
47 Correct 24 ms 47236 KB Output is correct
48 Correct 52 ms 58168 KB Output is correct
49 Correct 58 ms 58232 KB Output is correct
50 Correct 47 ms 58136 KB Output is correct
51 Correct 41 ms 58144 KB Output is correct
52 Correct 24 ms 47268 KB Output is correct
53 Correct 43 ms 58176 KB Output is correct
54 Correct 31 ms 47868 KB Output is correct
55 Correct 32 ms 48112 KB Output is correct
56 Correct 838 ms 96572 KB Output is correct
57 Correct 1332 ms 114864 KB Output is correct
58 Correct 1391 ms 115052 KB Output is correct
59 Correct 25 ms 47284 KB Output is correct
60 Correct 45 ms 58144 KB Output is correct
61 Correct 25 ms 47260 KB Output is correct
62 Correct 1659 ms 133636 KB Output is correct
63 Correct 1669 ms 133544 KB Output is correct
64 Correct 1678 ms 133284 KB Output is correct
65 Correct 33 ms 48340 KB Output is correct
66 Correct 43 ms 49428 KB Output is correct
67 Correct 845 ms 96672 KB Output is correct
68 Correct 1432 ms 117128 KB Output is correct
69 Correct 2083 ms 135480 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct
17 Correct 1623 ms 133948 KB Output is correct
18 Correct 1656 ms 133632 KB Output is correct
19 Correct 1922 ms 143088 KB Output is correct
20 Correct 1991 ms 134232 KB Output is correct
21 Correct 1660 ms 125296 KB Output is correct
22 Correct 40 ms 58212 KB Output is correct
23 Correct 203 ms 70360 KB Output is correct
24 Correct 80 ms 52188 KB Output is correct
25 Correct 360 ms 64376 KB Output is correct
26 Correct 742 ms 76552 KB Output is correct
27 Correct 811 ms 97336 KB Output is correct
28 Correct 1199 ms 107040 KB Output is correct
29 Correct 1455 ms 117000 KB Output is correct
30 Correct 1932 ms 126936 KB Output is correct
31 Correct 2075 ms 136912 KB Output is correct
32 Correct 1952 ms 134876 KB Output is correct
33 Correct 1661 ms 133832 KB Output is correct
34 Correct 42 ms 48492 KB Output is correct
35 Correct 47 ms 49612 KB Output is correct
36 Correct 850 ms 96632 KB Output is correct
37 Correct 1433 ms 117436 KB Output is correct
38 Correct 2025 ms 136168 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 58128 KB Output is correct
2 Correct 41 ms 58192 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 45 ms 58172 KB Output is correct
5 Correct 42 ms 58168 KB Output is correct
6 Correct 26 ms 47280 KB Output is correct
7 Correct 26 ms 47256 KB Output is correct
8 Correct 25 ms 47296 KB Output is correct
9 Correct 646 ms 95852 KB Output is correct
10 Correct 71 ms 61924 KB Output is correct
11 Correct 242 ms 78460 KB Output is correct
12 Correct 88 ms 63796 KB Output is correct
13 Correct 142 ms 59440 KB Output is correct
14 Correct 28 ms 47552 KB Output is correct
15 Correct 29 ms 47948 KB Output is correct
16 Correct 624 ms 95800 KB Output is correct
17 Correct 42 ms 58168 KB Output is correct
18 Correct 43 ms 58224 KB Output is correct
19 Correct 42 ms 58156 KB Output is correct
20 Correct 49 ms 58128 KB Output is correct
21 Correct 27 ms 47248 KB Output is correct
22 Correct 47 ms 58220 KB Output is correct
23 Correct 2321 ms 145892 KB Output is correct
24 Correct 46 ms 58172 KB Output is correct
25 Correct 48 ms 58684 KB Output is correct
26 Correct 33 ms 48124 KB Output is correct
27 Correct 36 ms 48432 KB Output is correct
28 Correct 761 ms 93092 KB Output is correct
29 Correct 1248 ms 110488 KB Output is correct
30 Correct 1802 ms 128420 KB Output is correct
31 Correct 2387 ms 145628 KB Output is correct
32 Correct 40 ms 58140 KB Output is correct
33 Correct 41 ms 58192 KB Output is correct
34 Correct 43 ms 58236 KB Output is correct
35 Correct 24 ms 47220 KB Output is correct
36 Correct 27 ms 47212 KB Output is correct
37 Correct 42 ms 58216 KB Output is correct
38 Correct 41 ms 58128 KB Output is correct
39 Correct 42 ms 58196 KB Output is correct
40 Correct 42 ms 58144 KB Output is correct
41 Correct 25 ms 47296 KB Output is correct
42 Correct 40 ms 58168 KB Output is correct
43 Correct 27 ms 47828 KB Output is correct
44 Correct 32 ms 48084 KB Output is correct
45 Correct 717 ms 96744 KB Output is correct
46 Correct 1186 ms 115828 KB Output is correct
47 Correct 1227 ms 115052 KB Output is correct
48 Correct 40 ms 58168 KB Output is correct
49 Correct 40 ms 58216 KB Output is correct
50 Correct 43 ms 58136 KB Output is correct
51 Correct 43 ms 58216 KB Output is correct
52 Correct 44 ms 58168 KB Output is correct
53 Correct 45 ms 58148 KB Output is correct
54 Correct 42 ms 58244 KB Output is correct
55 Correct 2651 ms 163588 KB Output is correct
56 Correct 42 ms 58168 KB Output is correct
57 Correct 51 ms 59056 KB Output is correct
58 Correct 71 ms 61284 KB Output is correct
59 Correct 64 ms 50620 KB Output is correct
60 Correct 1077 ms 111172 KB Output is correct
61 Correct 1621 ms 129508 KB Output is correct
62 Correct 2032 ms 145100 KB Output is correct
63 Correct 2596 ms 164192 KB Output is correct
64 Correct 23 ms 47316 KB Output is correct
65 Correct 40 ms 58200 KB Output is correct
66 Correct 22 ms 47292 KB Output is correct
67 Correct 1694 ms 133604 KB Output is correct
68 Correct 1683 ms 133568 KB Output is correct
69 Correct 1829 ms 133232 KB Output is correct
70 Correct 41 ms 48284 KB Output is correct
71 Correct 49 ms 49404 KB Output is correct
72 Correct 991 ms 96660 KB Output is correct
73 Correct 1745 ms 117440 KB Output is correct
74 Correct 2493 ms 135444 KB Output is correct
75 Correct 2346 ms 135696 KB Output is correct
76 Correct 1985 ms 133560 KB Output is correct
77 Correct 53 ms 48500 KB Output is correct
78 Correct 53 ms 49540 KB Output is correct
79 Correct 954 ms 96892 KB Output is correct
80 Correct 1663 ms 117504 KB Output is correct
81 Correct 2422 ms 135200 KB Output is correct
82 Correct 46 ms 58140 KB Output is correct
83 Correct 51 ms 58200 KB Output is correct
84 Correct 27 ms 47320 KB Output is correct
85 Correct 2059 ms 143244 KB Output is correct
86 Correct 2029 ms 139436 KB Output is correct
87 Correct 2009 ms 139108 KB Output is correct
88 Correct 1418 ms 121108 KB Output is correct
89 Correct 1238 ms 127180 KB Output is correct
90 Correct 1490 ms 102264 KB Output is correct
91 Correct 1349 ms 102080 KB Output is correct
92 Correct 1849 ms 133584 KB Output is correct
93 Correct 1786 ms 133548 KB Output is correct
94 Correct 1938 ms 133476 KB Output is correct
95 Correct 1989 ms 133544 KB Output is correct
96 Correct 41 ms 58168 KB Output is correct
97 Correct 118 ms 63744 KB Output is correct
98 Correct 477 ms 81116 KB Output is correct
99 Correct 1858 ms 141812 KB Output is correct
100 Correct 51 ms 49876 KB Output is correct
101 Correct 259 ms 60176 KB Output is correct
102 Correct 572 ms 72848 KB Output is correct
103 Correct 666 ms 89992 KB Output is correct
104 Correct 971 ms 101156 KB Output is correct
105 Correct 1359 ms 114412 KB Output is correct
106 Correct 1815 ms 126008 KB Output is correct
107 Correct 2118 ms 136552 KB Output is correct
108 Correct 42 ms 58168 KB Output is correct
109 Correct 48 ms 58128 KB Output is correct
110 Correct 47 ms 58208 KB Output is correct
111 Correct 25 ms 47336 KB Output is correct
112 Correct 24 ms 47236 KB Output is correct
113 Correct 52 ms 58168 KB Output is correct
114 Correct 58 ms 58232 KB Output is correct
115 Correct 47 ms 58136 KB Output is correct
116 Correct 41 ms 58144 KB Output is correct
117 Correct 24 ms 47268 KB Output is correct
118 Correct 43 ms 58176 KB Output is correct
119 Correct 31 ms 47868 KB Output is correct
120 Correct 32 ms 48112 KB Output is correct
121 Correct 838 ms 96572 KB Output is correct
122 Correct 1332 ms 114864 KB Output is correct
123 Correct 1391 ms 115052 KB Output is correct
124 Correct 25 ms 47284 KB Output is correct
125 Correct 45 ms 58144 KB Output is correct
126 Correct 25 ms 47260 KB Output is correct
127 Correct 1659 ms 133636 KB Output is correct
128 Correct 1669 ms 133544 KB Output is correct
129 Correct 1678 ms 133284 KB Output is correct
130 Correct 33 ms 48340 KB Output is correct
131 Correct 43 ms 49428 KB Output is correct
132 Correct 845 ms 96672 KB Output is correct
133 Correct 1432 ms 117128 KB Output is correct
134 Correct 2083 ms 135480 KB Output is correct
135 Correct 1623 ms 133948 KB Output is correct
136 Correct 1656 ms 133632 KB Output is correct
137 Correct 1922 ms 143088 KB Output is correct
138 Correct 1991 ms 134232 KB Output is correct
139 Correct 1660 ms 125296 KB Output is correct
140 Correct 40 ms 58212 KB Output is correct
141 Correct 203 ms 70360 KB Output is correct
142 Correct 80 ms 52188 KB Output is correct
143 Correct 360 ms 64376 KB Output is correct
144 Correct 742 ms 76552 KB Output is correct
145 Correct 811 ms 97336 KB Output is correct
146 Correct 1199 ms 107040 KB Output is correct
147 Correct 1455 ms 117000 KB Output is correct
148 Correct 1932 ms 126936 KB Output is correct
149 Correct 2075 ms 136912 KB Output is correct
150 Correct 1952 ms 134876 KB Output is correct
151 Correct 1661 ms 133832 KB Output is correct
152 Correct 42 ms 48492 KB Output is correct
153 Correct 47 ms 49612 KB Output is correct
154 Correct 850 ms 96632 KB Output is correct
155 Correct 1433 ms 117436 KB Output is correct
156 Correct 2025 ms 136168 KB Output is correct
157 Correct 50 ms 58168 KB Output is correct
158 Correct 23 ms 47280 KB Output is correct
159 Correct 42 ms 58176 KB Output is correct
160 Correct 42 ms 58212 KB Output is correct
161 Correct 3078 ms 178072 KB Output is correct
162 Correct 1786 ms 143496 KB Output is correct
163 Correct 2254 ms 143808 KB Output is correct
164 Correct 2207 ms 144564 KB Output is correct
165 Correct 2691 ms 163912 KB Output is correct
166 Correct 2873 ms 168084 KB Output is correct
167 Correct 459 ms 80692 KB Output is correct
168 Correct 203 ms 59592 KB Output is correct
169 Correct 674 ms 78816 KB Output is correct
170 Correct 1549 ms 106336 KB Output is correct
171 Correct 2181 ms 123188 KB Output is correct
172 Correct 1258 ms 114740 KB Output is correct
173 Correct 1575 ms 125880 KB Output is correct
174 Correct 1781 ms 137876 KB Output is correct
175 Correct 1942 ms 148120 KB Output is correct
176 Correct 2234 ms 160904 KB Output is correct
177 Correct 2587 ms 172196 KB Output is correct