oj.uz

Submission #1072048

# Submission time Handle Problem Language Result Execution time Memory
1072048 2024-08-23T13:42:11 Z shmax Fountain Parks (IOI21_parks) C++17
70 / 100
 2734 ms 83808 KB 
#include "parks.h"
#include <bits/stdc++.h>


#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

using i32 = int;
//#define int long long
#define len(x) (int)(x.size())
template<typename T>
using vec = vector<T>;

struct DSU {
public:
    DSU() : _n(0) {}

    explicit DSU(int n) : _n(n), parent_or_size(n, -1) {}

    int unite(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool one(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
                std::remove_if(result.begin(), result.end(),
                               [&](const std::vector<int> &v) { return v.empty(); }),
                result.end());
        return result;
    }

private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};


i32 construct_roads(std::vector<i32> _x, std::vector<i32> _y) {
    int n = len(_x);
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        mp[{_x[i], _y[i]}] = i;
    }
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    vec<pair<int, int>> edges;
    for (int i = 0; i < n; i++) {
        vec<pair<int, int>> moves = {{-2, 0},
                                     {2,  0}};
        for (auto [dx, dy]: moves) {
            int nx = _x[i] + dx;
            int ny = _y[i] + dy;
            if (!mp.count({nx, ny})) continue;
            edges.push_back({i, mp[{nx, ny}]});
        }
    }
    for (int i = 0; i < n; i++) {
        vec<pair<int, int>> moves = {{0, -2},
                                     {0, 2}};
        for (auto [dx, dy]: moves) {
            int nx = _x[i] + dx;
            int ny = _y[i] + dy;
            if (!mp.count({nx, ny})) continue;
            edges.push_back({i, mp[{nx, ny}]});
        }
    }
    for (int times = 0; times < 6; times++) {
        DSU dsu(n);
        reverse(edges.begin(), edges.end());
        if(times > 3){
            shuffle(edges.begin(), edges.end(), rnd);
        }
        vec<pair<int, int>> used_edges;
        for (auto [a, b]: edges) {
            if (dsu.one(a, b)) continue;
            dsu.unite(a, b);
            used_edges.emplace_back(a, b);
        }
        if (dsu.size(0) != n) return 0;
        shuffle(used_edges.begin(), used_edges.end(), rnd);
        map<pair<int, int>, int> benches;
        vec<pair<int, int>> benches_pos;
        int idx = 0;
        for (auto [a, b]: used_edges) {
            auto [x1, y1] = pair<int, int>{_x[a], _y[a]};
            auto [x2, y2] = pair<int, int>{_x[b], _y[b]};
            if (x1 == x2) {
                if (!benches.count({x1 - 1, (y1 + y2) / 2}))
                    benches[{x1 - 1, (y1 + y2) / 2}] = idx++, benches_pos.emplace_back(x1 - 1, (y1 + y2) / 2);
                if (!benches.count({x1 + 1, (y1 + y2) / 2}))
                    benches[{x1 + 1, (y1 + y2) / 2}] = idx++, benches_pos.emplace_back(x1 + 1, (y1 + y2) / 2);
            } else {
                if (!benches.count({(x1 + x2) / 2, y1 - 1}))
                    benches[{(x1 + x2) / 2, y1 - 1}] = idx++, benches_pos.emplace_back((x1 + x2) / 2, y1 - 1);
                if (!benches.count({(x1 + x2) / 2, y1 + 1}))
                    benches[{(x1 + x2) / 2, y1 + 1}] = idx++, benches_pos.emplace_back((x1 + x2) / 2, y1 + 1);
            }
        }
        vec<vec<int>> g(n - 1 + len(benches));
        int idt = 0;
        for (auto [a, b]: used_edges) {
            auto [x1, y1] = pair<int, int>{_x[a], _y[a]};
            auto [x2, y2] = pair<int, int>{_x[b], _y[b]};
            if (x1 == x2) {
                g[idt].push_back(n - 1 + benches[{x1 - 1, (y1 + y2) / 2}]);
                g[idt].push_back(n - 1 + benches[{x1 + 1, (y1 + y2) / 2}]);
            } else {
                g[idt].push_back(n - 1 + benches[{(x1 + x2) / 2, y1 - 1}]);
                g[idt].push_back(n - 1 + benches[{(x1 + x2) / 2, y1 + 1}]);
            }
            idt++;
        }

//        matching
//        shuffle
        for (int i = 0; i < n - 1; i++) {
            shuffle(g[i].begin(), g[i].end(), rnd);
        }

        vec<int> match(n - 1 + len(benches), -1);
        vec<bool> used(n - 1 + len(benches), false);
        function<bool(int)> dfs = [&](int v) -> bool {
            if (used[v]) return false;
            used[v] = true;
            for (auto u: g[v]) {
                if (match[u] == -1 || dfs(match[u])) {
                    match[u] = v;
                    match[v] = u;
                    return true;
                }
            }
            return false;
        };

        bool flag = true;
        do {
            flag = false;
            fill(used.begin(), used.end(), false);
            for (int i = 0; i < n - 1; i++) {
                if (match[i] == -1) {
                    if (dfs(i)) {
                        flag = true;
                    }
                }
            }
        } while (flag);

        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            if (match[i] != -1) cnt++;
        }

        if (cnt == n - 1) {
            vec<i32> x_benches, y_benches;
            vec<i32> u, v;
            for (int i = 0; i < n - 1; i++) {
                x_benches.push_back(benches_pos[match[i] - n + 1].first);
                y_benches.push_back(benches_pos[match[i] - n + 1].second);
                u.push_back(used_edges[i].first);
                v.push_back(used_edges[i].second);
            }
            build(u, v, x_benches, y_benches);
            return 1;
        }


    }

    return 0;
}

Compilation message

parks.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 703 ms 77120 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 226 ms 30284 KB Output is correct
29 Correct 372 ms 44520 KB Output is correct
30 Correct 541 ms 60424 KB Output is correct
31 Correct 710 ms 76100 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 281 ms 35364 KB Output is correct
46 Correct 446 ms 53168 KB Output is correct
47 Correct 455 ms 52928 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 703 ms 77120 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 226 ms 30284 KB Output is correct
29 Correct 372 ms 44520 KB Output is correct
30 Correct 541 ms 60424 KB Output is correct
31 Correct 710 ms 76100 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 281 ms 35364 KB Output is correct
46 Correct 446 ms 53168 KB Output is correct
47 Correct 455 ms 52928 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 752 ms 73752 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 3 ms 884 KB Output is correct
58 Correct 13 ms 2520 KB Output is correct
59 Correct 12 ms 1760 KB Output is correct
60 Correct 356 ms 36284 KB Output is correct
61 Correct 466 ms 49344 KB Output is correct
62 Correct 586 ms 61192 KB Output is correct
63 Correct 785 ms 74544 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 699 ms 82436 KB Output is correct
68 Correct 653 ms 82624 KB Output is correct
69 Correct 687 ms 83808 KB Output is correct
70 Correct 4 ms 856 KB Output is correct
71 Correct 8 ms 1372 KB Output is correct
72 Correct 283 ms 34916 KB Output is correct
73 Correct 495 ms 52924 KB Output is correct
74 Correct 762 ms 71872 KB Output is correct
75 Correct 793 ms 75712 KB Output is correct
76 Correct 774 ms 83652 KB Output is correct
77 Correct 5 ms 840 KB Output is correct
78 Correct 12 ms 1496 KB Output is correct
79 Correct 353 ms 36096 KB Output is correct
80 Correct 619 ms 56000 KB Output is correct
81 Correct 866 ms 71844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 875 ms 71364 KB Output is correct
21 Correct 902 ms 66116 KB Output is correct
22 Correct 1020 ms 71992 KB Output is correct
23 Correct 787 ms 71980 KB Output is correct
24 Correct 286 ms 16856 KB Output is correct
25 Correct 562 ms 23572 KB Output is correct
26 Correct 361 ms 23792 KB Output is correct
27 Correct 886 ms 82500 KB Output is correct
28 Correct 832 ms 82884 KB Output is correct
29 Correct 911 ms 82368 KB Output is correct
30 Correct 943 ms 82480 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 32 ms 5032 KB Output is correct
33 Correct 121 ms 8508 KB Output is correct
34 Correct 784 ms 65736 KB Output is correct
35 Correct 11 ms 1504 KB Output is correct
36 Correct 83 ms 6112 KB Output is correct
37 Correct 166 ms 11972 KB Output is correct
38 Correct 275 ms 27148 KB Output is correct
39 Correct 400 ms 36716 KB Output is correct
40 Correct 619 ms 49108 KB Output is correct
41 Correct 730 ms 57428 KB Output is correct
42 Correct 756 ms 66664 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 3 ms 688 KB Output is correct
56 Correct 292 ms 35384 KB Output is correct
57 Correct 456 ms 53316 KB Output is correct
58 Correct 469 ms 52924 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 644 ms 83756 KB Output is correct
63 Correct 657 ms 82880 KB Output is correct
64 Correct 630 ms 82108 KB Output is correct
65 Correct 4 ms 856 KB Output is correct
66 Correct 7 ms 1372 KB Output is correct
67 Correct 290 ms 34832 KB Output is correct
68 Correct 493 ms 53436 KB Output is correct
69 Correct 831 ms 72180 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct
17 Correct 751 ms 82592 KB Output is correct
18 Correct 747 ms 82624 KB Output is correct
19 Correct 748 ms 71508 KB Output is correct
20 Correct 807 ms 69224 KB Output is correct
21 Correct 723 ms 68220 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 94 ms 10884 KB Output is correct
24 Correct 24 ms 2768 KB Output is correct
25 Correct 114 ms 9024 KB Output is correct
26 Correct 196 ms 14316 KB Output is correct
27 Correct 323 ms 34756 KB Output is correct
28 Correct 446 ms 43768 KB Output is correct
29 Correct 594 ms 52764 KB Output is correct
30 Correct 698 ms 60800 KB Output is correct
31 Correct 821 ms 69296 KB Output is correct
32 Correct 752 ms 75452 KB Output is correct
33 Correct 698 ms 82456 KB Output is correct
34 Correct 5 ms 860 KB Output is correct
35 Correct 9 ms 1452 KB Output is correct
36 Correct 353 ms 35996 KB Output is correct
37 Correct 553 ms 55788 KB Output is correct
38 Correct 823 ms 71804 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 256 ms 41412 KB Output is correct
10 Correct 19 ms 4440 KB Output is correct
11 Correct 122 ms 22476 KB Output is correct
12 Correct 33 ms 6476 KB Output is correct
13 Correct 32 ms 5580 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 263 ms 41332 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 703 ms 77120 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 226 ms 30284 KB Output is correct
29 Correct 372 ms 44520 KB Output is correct
30 Correct 541 ms 60424 KB Output is correct
31 Correct 710 ms 76100 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 281 ms 35364 KB Output is correct
46 Correct 446 ms 53168 KB Output is correct
47 Correct 455 ms 52928 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 752 ms 73752 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 3 ms 884 KB Output is correct
58 Correct 13 ms 2520 KB Output is correct
59 Correct 12 ms 1760 KB Output is correct
60 Correct 356 ms 36284 KB Output is correct
61 Correct 466 ms 49344 KB Output is correct
62 Correct 586 ms 61192 KB Output is correct
63 Correct 785 ms 74544 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 699 ms 82436 KB Output is correct
68 Correct 653 ms 82624 KB Output is correct
69 Correct 687 ms 83808 KB Output is correct
70 Correct 4 ms 856 KB Output is correct
71 Correct 8 ms 1372 KB Output is correct
72 Correct 283 ms 34916 KB Output is correct
73 Correct 495 ms 52924 KB Output is correct
74 Correct 762 ms 71872 KB Output is correct
75 Correct 793 ms 75712 KB Output is correct
76 Correct 774 ms 83652 KB Output is correct
77 Correct 5 ms 840 KB Output is correct
78 Correct 12 ms 1496 KB Output is correct
79 Correct 353 ms 36096 KB Output is correct
80 Correct 619 ms 56000 KB Output is correct
81 Correct 866 ms 71844 KB Output is correct
82 Correct 0 ms 344 KB Output is correct
83 Correct 0 ms 348 KB Output is correct
84 Correct 1 ms 348 KB Output is correct
85 Correct 875 ms 71364 KB Output is correct
86 Correct 902 ms 66116 KB Output is correct
87 Correct 1020 ms 71992 KB Output is correct
88 Correct 787 ms 71980 KB Output is correct
89 Correct 286 ms 16856 KB Output is correct
90 Correct 562 ms 23572 KB Output is correct
91 Correct 361 ms 23792 KB Output is correct
92 Correct 886 ms 82500 KB Output is correct
93 Correct 832 ms 82884 KB Output is correct
94 Correct 911 ms 82368 KB Output is correct
95 Correct 943 ms 82480 KB Output is correct
96 Correct 0 ms 348 KB Output is correct
97 Correct 32 ms 5032 KB Output is correct
98 Correct 121 ms 8508 KB Output is correct
99 Correct 784 ms 65736 KB Output is correct
100 Correct 11 ms 1504 KB Output is correct
101 Correct 83 ms 6112 KB Output is correct
102 Correct 166 ms 11972 KB Output is correct
103 Correct 275 ms 27148 KB Output is correct
104 Correct 400 ms 36716 KB Output is correct
105 Correct 619 ms 49108 KB Output is correct
106 Correct 730 ms 57428 KB Output is correct
107 Correct 756 ms 66664 KB Output is correct
108 Correct 1 ms 344 KB Output is correct
109 Correct 0 ms 348 KB Output is correct
110 Correct 0 ms 348 KB Output is correct
111 Correct 1 ms 348 KB Output is correct
112 Correct 0 ms 348 KB Output is correct
113 Correct 0 ms 348 KB Output is correct
114 Correct 0 ms 348 KB Output is correct
115 Correct 0 ms 348 KB Output is correct
116 Correct 0 ms 348 KB Output is correct
117 Correct 0 ms 348 KB Output is correct
118 Correct 0 ms 348 KB Output is correct
119 Correct 2 ms 604 KB Output is correct
120 Correct 3 ms 688 KB Output is correct
121 Correct 292 ms 35384 KB Output is correct
122 Correct 456 ms 53316 KB Output is correct
123 Correct 469 ms 52924 KB Output is correct
124 Correct 1 ms 348 KB Output is correct
125 Correct 0 ms 348 KB Output is correct
126 Correct 0 ms 348 KB Output is correct
127 Correct 644 ms 83756 KB Output is correct
128 Correct 657 ms 82880 KB Output is correct
129 Correct 630 ms 82108 KB Output is correct
130 Correct 4 ms 856 KB Output is correct
131 Correct 7 ms 1372 KB Output is correct
132 Correct 290 ms 34832 KB Output is correct
133 Correct 493 ms 53436 KB Output is correct
134 Correct 831 ms 72180 KB Output is correct
135 Correct 751 ms 82592 KB Output is correct
136 Correct 747 ms 82624 KB Output is correct
137 Correct 748 ms 71508 KB Output is correct
138 Correct 807 ms 69224 KB Output is correct
139 Correct 723 ms 68220 KB Output is correct
140 Correct 0 ms 600 KB Output is correct
141 Correct 94 ms 10884 KB Output is correct
142 Correct 24 ms 2768 KB Output is correct
143 Correct 114 ms 9024 KB Output is correct
144 Correct 196 ms 14316 KB Output is correct
145 Correct 323 ms 34756 KB Output is correct
146 Correct 446 ms 43768 KB Output is correct
147 Correct 594 ms 52764 KB Output is correct
148 Correct 698 ms 60800 KB Output is correct
149 Correct 821 ms 69296 KB Output is correct
150 Correct 752 ms 75452 KB Output is correct
151 Correct 698 ms 82456 KB Output is correct
152 Correct 5 ms 860 KB Output is correct
153 Correct 9 ms 1452 KB Output is correct
154 Correct 353 ms 35996 KB Output is correct
155 Correct 553 ms 55788 KB Output is correct
156 Correct 823 ms 71804 KB Output is correct
157 Correct 1 ms 344 KB Output is correct
158 Correct 0 ms 348 KB Output is correct
159 Correct 1 ms 348 KB Output is correct
160 Correct 0 ms 348 KB Output is correct
161 Incorrect 2734 ms 57016 KB Solution announced impossible, but it is possible.
162 Halted 0 ms 0 KB -