oj.uz

Submission #198103

# Submission time Handle Problem Language Result Execution time Memory
198103 2020-01-24T18:00:18 Z model_code Building Skyscrapers (CEOI19_skyscrapers) C++17
100 / 100
 2782 ms 324140 KB 
/* Constructs the minimum required grid graph.
   Tracks connected components using union-find.
   Decides which cells may be deleted based on neighbourhoods,
   updates that information when necessary and keeps these cells
   in a set<>.
   O(N log N)
*/
#include <bits/stdc++.h>
using namespace std;

class HashPair {
    static inline size_t hash_combine(size_t h_first, size_t h_second) {
        return h_first ^ (h_second + 0x9e3779b9 + (h_first << 6) + (h_second >> 2));
    }

    static inline size_t hash_int(unsigned int x) {
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = (x >> 16) ^ x;
        return x;
    }

public:
    size_t operator() (const pair<int, int> & p) const {
        size_t h_first  = hash_int(p.first);
        size_t h_second = hash_int(p.second);

        return hash_combine(h_first, h_second);
    }
};

class lego {
    int N, V;
    vector< pair<int, int> > cells, empty_cells;
    unordered_map< pair<int, int>, int, HashPair> cell_indices, empty_cell_indices;
    vector<char> removed;

    set<int> removable;
    vector<char> is_removable;

    vector< vector<int> > G4, G8;

    void construct_graphs(bool only_solvability = false) {
        constexpr static int dx[8] = {-1, -1, -1,  0,  1, 1, 1, 0};
        constexpr static int dy[8] = { 1,  0, -1, -1, -1, 0, 1, 1};

        if(!init_solvability_done) {
            for(int i = 0; i < N; i++) for(int j = 0; j < 8; j++) {
                pair<int, int> p = {cells[i].first + dx[j], cells[i].second + dy[j]};
                auto it = cell_indices.find(p);
                int cell_id = (it == end(cell_indices)) ? -1 : it->second;
                if(cell_id == -1) {
                    auto jt = empty_cell_indices.find(p);
                    if(jt == end(empty_cell_indices)) {
                        empty_cell_indices[p] = empty_cells.size();
                        cell_id = N + empty_cells.size();
                        empty_cells.push_back(p);
                        G4.push_back({});
                        G8.push_back(vector<int>(8, cell_id));
                    }
                    else cell_id = N + jt->second;
                    G8[cell_id][4^j] = i;
                    if(j % 2) G4[cell_id].push_back(i);
                }
                G8[i][j] = cell_id;
                if(j % 2) G4[i].push_back(cell_id);
            }
        }
        if(!init_done && !only_solvability) {
            for(int i = 0; i < (int)empty_cells.size(); i++) for(int j = 0; j < 8; j++) {
                if(G8[N+i][j] != N+i) continue;
                pair<int, int> p = {empty_cells[i].first + dx[j], empty_cells[i].second + dy[j]};
                auto it = empty_cell_indices.find(p);
                if(it == end(empty_cell_indices)) continue;
                int cell_id = N + it->second;
                G8[N+i][j] = cell_id;
                if(j % 2) G4[N+i].push_back(cell_id);
            }
        }
    }

    int outer_component;
    vector< vector<int> > components4, components8;
    vector<int> comp4, comp8;
    vector<int> deg4, deg8; // degree = number of full neighbouring cells

    void find_components(bool only_solvability = false) {
        queue<int> q;

        if(!init_solvability_done) {
            components4.clear(); components4.resize(V);
            components8.clear(); components8.resize(V);
            comp4.clear(); comp4.resize(V, -1);
            comp8.clear(); comp8.resize(V, -1);
            deg4.clear(); deg4.resize(V, 0);
            deg8.clear(); deg8.resize(V, 0);
            for(int i = 0; i < V; i++) if(comp8[i] == -1 && !is_empty(i)) {
                comp8[i] = i;
                components8[i] = {i};
                q.push(i);
                while(!q.empty()) {
                    for(auto v : G8[q.front()]) if(comp8[v] == -1 && !is_empty(v)) {
                        comp8[v] = i;
                        components8[i].push_back(v);
                        q.push(v);
                    } 
                    q.pop();
                }
            }
        }
        if(!init_done && !only_solvability) {
            for(int i = 0; i < V; i++) if(comp4[i] == -1 && is_empty(i)) {
                comp4[i] = i;
                components4[i] = {i};
                q.push(i);
                while(!q.empty()) {
                    for(auto v : G4[q.front()]) if(comp4[v] == -1 && is_empty(v)) {
                        comp4[v] = i;
                        components4[i].push_back(v);
                        q.push(v);
                    } 
                    q.pop();
                }
            }
            for(int i = 0; i < V; i++) {
                for(auto v : G4[i]) if(!is_empty(v)) deg4[i]++;
                for(auto v : G8[i]) if(!is_empty(v)) deg8[i]++;
            }
        }
    }

    void add_edge(int v1, int v2) {
        int c1 = comp4[v1], c2 = comp4[v2];
        if(c1 == c2) return;
        if(components4[c1].size() < components4[c2].size()) swap(c1, c2);
        for(auto v : components4[c2]) {
            comp4[v] = c1;
            components4[c1].push_back(v);
        }
        if(c2 == outer_component) outer_component = c1;
        for(auto v : components4[c2])
            for(auto f : G8[v]) if(!is_empty(f)) update(f);
    }

    void update(int v) {
        static vector<char> seen = vector<char>(V, 0);

        bool reachable = false, articulation = false;

        for(auto adj : G4[v]) if(is_empty(adj))
            if(comp4[adj] == outer_component) reachable = true;

        if(deg8[v] <= 1) {
            if(reachable) {
                if(!is_removable[v]) {
                    removable.insert(v);
                    is_removable[v] = 1;
                }
            }
            else if(is_removable[v]) {
                removable.erase(v);
                is_removable[v] = 0;
            }
            return;
        }

        for(int j = 0; j < 8; j++) if(is_empty(G8[v][j])) {
            if(is_empty(G8[v][(j+1)%8])) continue; // 1 cell per region
            if(j % 2 == 0 && !is_empty(G8[v][(j+7)%8])) continue; // ignore corner gaps
            int c = comp4[G8[v][j]];
            if(seen[c]) {
                articulation = true;
                break;
            }
            seen[c]++;
        }
        for(int j = 0; j < 8; j++) if(is_empty(G8[v][j]))
            seen[comp4[G8[v][j]]] = 0;

        if(reachable && !articulation) {
            if(!is_removable[v]) {
                removable.insert(v);
                is_removable[v] = 1;
            }
        }
        else if(is_removable[v]) {
            removable.erase(v);
            is_removable[v] = 0;
        }
    }

    inline bool is_empty(int cell) {
        return (cell >= N || removed[cell]);
    }

    bool init_done, init_solvability_done;

    void init_solvability() {
        if(init_solvability_done) return;
        construct_graphs(true);
        V = G4.size();
        removed.resize(V, false);
        find_components(true);
        init_solvability_done = true;
    }

    void init() {
        if(init_done) return;

        construct_graphs();
        if(!init_solvability_done) {
            V = G4.size();
            removed.resize(V, false);
        }

        find_components();
        int min_coord = cells[0].first;
        for(int i = N; i < V; i++) if(min_coord >= empty_cells[i-N].first) {
            min_coord = empty_cells[i-N].first;
            outer_component = comp4[i];
        }

        is_removable.resize(N, 0);
        for(int i = 0; i < N; i++) update(i);
        
        init_done = init_solvability_done = true;
    }

  public:
    lego(vector< pair<int, int> > cells_) : N(cells_.size()), cells(cells_) {
        for(int i = 0; i < N; i++) cell_indices[cells[i]] = i;
        G4.resize(N);
        G8.resize(N, vector<int>(8));
        G4.reserve(9*N);
        G8.reserve(9*N);
        cell_indices.reserve(N);
        empty_cell_indices.reserve(8*N);
        
        init_done = init_solvability_done = false;
    }
    
    bool solvable() {
        init_solvability();
        return ((int)components8[comp8[0]].size() == N);
    }

    int remove() {
        init();
        if(removable.empty()) return -1;
        int rm_id = *rbegin(removable);

        removable.erase(--end(removable));
        removed[rm_id] = true;

        components4[rm_id] = {rm_id};
        comp4[rm_id] = rm_id;
        for(auto f : G4[rm_id]) if(!is_empty(f)) update(f);
        for(auto v : G4[rm_id]) {
            if(is_empty(v)) add_edge(rm_id, v);
            else deg4[v]--;
        }
        for(auto v : G8[rm_id]) {
            deg8[v]--;
            if(!is_empty(v)) update(v);
        }

        return rm_id;
    }
};

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, t;
    cin >> N >> t;
    vector< pair<int, int> > cells(N);
    for(int i = 0; i < N; i++) cin >> cells[i].first >> cells[i].second;

    lego solver(cells);

    if(!solver.solvable()) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    vector<int> build;
    for(int i = 0; i < N; i++) {
        int removed_cell_id = solver.remove();
        assert(removed_cell_id != -1);
        build.push_back(removed_cell_id+1);
    }
    reverse(begin(build), end(build));
    for(int i = 0; i < N; i++) cout << build[i] << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 6 ms 452 KB ans=NO N=4
4 Correct 2 ms 508 KB ans=YES N=5
5 Correct 2 ms 376 KB ans=YES N=9
6 Correct 2 ms 248 KB ans=YES N=5
7 Correct 9 ms 348 KB ans=NO N=9
8 Correct 2 ms 348 KB ans=NO N=10
9 Correct 3 ms 376 KB ans=YES N=10
10 Correct 2 ms 376 KB ans=YES N=10
11 Correct 2 ms 376 KB ans=YES N=10
12 Correct 2 ms 376 KB ans=YES N=9
13 Correct 2 ms 376 KB ans=YES N=9
14 Correct 2 ms 376 KB ans=YES N=8
15 Correct 2 ms 376 KB ans=YES N=8
16 Correct 2 ms 376 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 6 ms 452 KB ans=NO N=4
4 Correct 2 ms 508 KB ans=YES N=5
5 Correct 2 ms 376 KB ans=YES N=9
6 Correct 2 ms 248 KB ans=YES N=5
7 Correct 9 ms 348 KB ans=NO N=9
8 Correct 2 ms 348 KB ans=NO N=10
9 Correct 3 ms 376 KB ans=YES N=10
10 Correct 2 ms 376 KB ans=YES N=10
11 Correct 2 ms 376 KB ans=YES N=10
12 Correct 2 ms 376 KB ans=YES N=9
13 Correct 2 ms 376 KB ans=YES N=9
14 Correct 2 ms 376 KB ans=YES N=8
15 Correct 2 ms 376 KB ans=YES N=8
16 Correct 2 ms 376 KB ans=NO N=2
17 Correct 2 ms 376 KB ans=YES N=17
18 Correct 0 ms 376 KB ans=YES N=25
19 Correct 2 ms 348 KB ans=YES N=100
20 Correct 3 ms 376 KB ans=YES N=185
21 Correct 3 ms 632 KB ans=NO N=174
22 Correct 3 ms 376 KB ans=YES N=90
23 Correct 2 ms 376 KB ans=YES N=63
24 Correct 3 ms 504 KB ans=YES N=87
25 Correct 3 ms 504 KB ans=YES N=183
26 Correct 3 ms 376 KB ans=YES N=188
27 Correct 3 ms 508 KB ans=YES N=183
28 Correct 8 ms 504 KB ans=YES N=189
29 Correct 8 ms 504 KB ans=YES N=200
30 Correct 0 ms 504 KB ans=YES N=190
31 Correct 3 ms 504 KB ans=YES N=187
32 Correct 3 ms 420 KB ans=YES N=187
33 Correct 3 ms 504 KB ans=YES N=182
34 Correct 3 ms 412 KB ans=YES N=184
35 Correct 9 ms 476 KB ans=YES N=188
36 Correct 4 ms 544 KB ans=YES N=181
37 Correct 3 ms 376 KB ans=YES N=188
38 Correct 3 ms 504 KB ans=YES N=191
39 Correct 7 ms 504 KB ans=YES N=196
40 Correct 3 ms 504 KB ans=YES N=196
41 Correct 6 ms 476 KB ans=YES N=196
42 Correct 3 ms 424 KB ans=YES N=196
43 Correct 3 ms 504 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 6 ms 452 KB ans=NO N=4
4 Correct 2 ms 508 KB ans=YES N=5
5 Correct 2 ms 376 KB ans=YES N=9
6 Correct 2 ms 248 KB ans=YES N=5
7 Correct 9 ms 348 KB ans=NO N=9
8 Correct 2 ms 348 KB ans=NO N=10
9 Correct 3 ms 376 KB ans=YES N=10
10 Correct 2 ms 376 KB ans=YES N=10
11 Correct 2 ms 376 KB ans=YES N=10
12 Correct 2 ms 376 KB ans=YES N=9
13 Correct 2 ms 376 KB ans=YES N=9
14 Correct 2 ms 376 KB ans=YES N=8
15 Correct 2 ms 376 KB ans=YES N=8
16 Correct 2 ms 376 KB ans=NO N=2
17 Correct 2 ms 376 KB ans=YES N=17
18 Correct 0 ms 376 KB ans=YES N=25
19 Correct 2 ms 348 KB ans=YES N=100
20 Correct 3 ms 376 KB ans=YES N=185
21 Correct 3 ms 632 KB ans=NO N=174
22 Correct 3 ms 376 KB ans=YES N=90
23 Correct 2 ms 376 KB ans=YES N=63
24 Correct 3 ms 504 KB ans=YES N=87
25 Correct 3 ms 504 KB ans=YES N=183
26 Correct 3 ms 376 KB ans=YES N=188
27 Correct 3 ms 508 KB ans=YES N=183
28 Correct 8 ms 504 KB ans=YES N=189
29 Correct 8 ms 504 KB ans=YES N=200
30 Correct 0 ms 504 KB ans=YES N=190
31 Correct 3 ms 504 KB ans=YES N=187
32 Correct 3 ms 420 KB ans=YES N=187
33 Correct 3 ms 504 KB ans=YES N=182
34 Correct 3 ms 412 KB ans=YES N=184
35 Correct 9 ms 476 KB ans=YES N=188
36 Correct 4 ms 544 KB ans=YES N=181
37 Correct 3 ms 376 KB ans=YES N=188
38 Correct 3 ms 504 KB ans=YES N=191
39 Correct 7 ms 504 KB ans=YES N=196
40 Correct 3 ms 504 KB ans=YES N=196
41 Correct 6 ms 476 KB ans=YES N=196
42 Correct 3 ms 424 KB ans=YES N=196
43 Correct 3 ms 504 KB ans=YES N=195
44 Correct 13 ms 4600 KB ans=NO N=1934
45 Correct 8 ms 1912 KB ans=NO N=1965
46 Correct 9 ms 1144 KB ans=YES N=1824
47 Correct 11 ms 1184 KB ans=YES N=1981
48 Correct 10 ms 1144 KB ans=YES N=1814
49 Correct 13 ms 1252 KB ans=YES N=1854
50 Correct 11 ms 1192 KB ans=YES N=1831
51 Correct 12 ms 1124 KB ans=YES N=2000
52 Correct 14 ms 1400 KB ans=YES N=1847
53 Correct 13 ms 1528 KB ans=YES N=1819
54 Correct 11 ms 1320 KB ans=YES N=1986
55 Correct 16 ms 1912 KB ans=YES N=2000
56 Correct 10 ms 2140 KB ans=YES N=1834
57 Correct 16 ms 2124 KB ans=YES N=1860
58 Correct 15 ms 2168 KB ans=YES N=1898
59 Correct 12 ms 1784 KB ans=YES N=1832
60 Correct 15 ms 2492 KB ans=YES N=1929
61 Correct 13 ms 1372 KB ans=YES N=1919
62 Correct 15 ms 2040 KB ans=YES N=1882
63 Correct 17 ms 2552 KB ans=YES N=1922
64 Correct 11 ms 1528 KB ans=YES N=1989
65 Correct 10 ms 1812 KB ans=YES N=1978
66 Correct 11 ms 1912 KB ans=YES N=1867
67 Correct 15 ms 1784 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4600 KB ans=NO N=1934
2 Correct 8 ms 1872 KB ans=NO N=1965
3 Correct 10 ms 1116 KB ans=YES N=1824
4 Correct 11 ms 1272 KB ans=YES N=1981
5 Correct 12 ms 1144 KB ans=YES N=1814
6 Correct 12 ms 1272 KB ans=YES N=1854
7 Correct 10 ms 1144 KB ans=YES N=1831
8 Correct 12 ms 1276 KB ans=YES N=2000
9 Correct 14 ms 1500 KB ans=YES N=1847
10 Correct 13 ms 1528 KB ans=YES N=1819
11 Correct 10 ms 1272 KB ans=YES N=1986
12 Correct 16 ms 1912 KB ans=YES N=2000
13 Correct 15 ms 2168 KB ans=YES N=1834
14 Correct 16 ms 2040 KB ans=YES N=1860
15 Correct 16 ms 2168 KB ans=YES N=1898
16 Correct 14 ms 1756 KB ans=YES N=1832
17 Correct 15 ms 2552 KB ans=YES N=1929
18 Correct 13 ms 1376 KB ans=YES N=1919
19 Correct 15 ms 2040 KB ans=YES N=1882
20 Correct 15 ms 2552 KB ans=YES N=1922
21 Correct 11 ms 1528 KB ans=YES N=1989
22 Correct 10 ms 1784 KB ans=YES N=1978
23 Correct 11 ms 1912 KB ans=YES N=1867

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 6 ms 452 KB ans=NO N=4
4 Correct 2 ms 508 KB ans=YES N=5
5 Correct 2 ms 376 KB ans=YES N=9
6 Correct 2 ms 248 KB ans=YES N=5
7 Correct 9 ms 348 KB ans=NO N=9
8 Correct 2 ms 348 KB ans=NO N=10
9 Correct 3 ms 376 KB ans=YES N=10
10 Correct 2 ms 376 KB ans=YES N=10
11 Correct 2 ms 376 KB ans=YES N=10
12 Correct 2 ms 376 KB ans=YES N=9
13 Correct 2 ms 376 KB ans=YES N=9
14 Correct 2 ms 376 KB ans=YES N=8
15 Correct 2 ms 376 KB ans=YES N=8
16 Correct 2 ms 376 KB ans=NO N=2
17 Correct 2 ms 376 KB ans=YES N=17
18 Correct 0 ms 376 KB ans=YES N=25
19 Correct 2 ms 348 KB ans=YES N=100
20 Correct 3 ms 376 KB ans=YES N=185
21 Correct 3 ms 632 KB ans=NO N=174
22 Correct 3 ms 376 KB ans=YES N=90
23 Correct 2 ms 376 KB ans=YES N=63
24 Correct 3 ms 504 KB ans=YES N=87
25 Correct 3 ms 504 KB ans=YES N=183
26 Correct 3 ms 376 KB ans=YES N=188
27 Correct 3 ms 508 KB ans=YES N=183
28 Correct 8 ms 504 KB ans=YES N=189
29 Correct 8 ms 504 KB ans=YES N=200
30 Correct 0 ms 504 KB ans=YES N=190
31 Correct 3 ms 504 KB ans=YES N=187
32 Correct 3 ms 420 KB ans=YES N=187
33 Correct 3 ms 504 KB ans=YES N=182
34 Correct 3 ms 412 KB ans=YES N=184
35 Correct 9 ms 476 KB ans=YES N=188
36 Correct 4 ms 544 KB ans=YES N=181
37 Correct 3 ms 376 KB ans=YES N=188
38 Correct 3 ms 504 KB ans=YES N=191
39 Correct 7 ms 504 KB ans=YES N=196
40 Correct 3 ms 504 KB ans=YES N=196
41 Correct 6 ms 476 KB ans=YES N=196
42 Correct 3 ms 424 KB ans=YES N=196
43 Correct 3 ms 504 KB ans=YES N=195
44 Correct 13 ms 4600 KB ans=NO N=1934
45 Correct 8 ms 1912 KB ans=NO N=1965
46 Correct 9 ms 1144 KB ans=YES N=1824
47 Correct 11 ms 1184 KB ans=YES N=1981
48 Correct 10 ms 1144 KB ans=YES N=1814
49 Correct 13 ms 1252 KB ans=YES N=1854
50 Correct 11 ms 1192 KB ans=YES N=1831
51 Correct 12 ms 1124 KB ans=YES N=2000
52 Correct 14 ms 1400 KB ans=YES N=1847
53 Correct 13 ms 1528 KB ans=YES N=1819
54 Correct 11 ms 1320 KB ans=YES N=1986
55 Correct 16 ms 1912 KB ans=YES N=2000
56 Correct 10 ms 2140 KB ans=YES N=1834
57 Correct 16 ms 2124 KB ans=YES N=1860
58 Correct 15 ms 2168 KB ans=YES N=1898
59 Correct 12 ms 1784 KB ans=YES N=1832
60 Correct 15 ms 2492 KB ans=YES N=1929
61 Correct 13 ms 1372 KB ans=YES N=1919
62 Correct 15 ms 2040 KB ans=YES N=1882
63 Correct 17 ms 2552 KB ans=YES N=1922
64 Correct 11 ms 1528 KB ans=YES N=1989
65 Correct 10 ms 1812 KB ans=YES N=1978
66 Correct 11 ms 1912 KB ans=YES N=1867
67 Correct 15 ms 1784 KB ans=YES N=1942
68 Correct 350 ms 31964 KB ans=NO N=66151
69 Correct 645 ms 111604 KB ans=NO N=64333
70 Correct 412 ms 27636 KB ans=YES N=69316
71 Correct 391 ms 26616 KB ans=YES N=66695
72 Correct 419 ms 27388 KB ans=YES N=68436
73 Correct 433 ms 28044 KB ans=YES N=70000
74 Correct 452 ms 27820 KB ans=YES N=68501
75 Correct 517 ms 29156 KB ans=YES N=70000
76 Correct 620 ms 30732 KB ans=YES N=65009
77 Correct 945 ms 48960 KB ans=YES N=67007
78 Correct 954 ms 56520 KB ans=YES N=66357
79 Correct 1010 ms 62432 KB ans=YES N=65430
80 Correct 992 ms 60324 KB ans=YES N=65790
81 Correct 973 ms 56192 KB ans=YES N=66020
82 Correct 934 ms 51876 KB ans=YES N=65809
83 Correct 641 ms 35736 KB ans=YES N=65651
84 Correct 1137 ms 78204 KB ans=YES N=68040
85 Correct 1020 ms 68468 KB ans=YES N=66570
86 Correct 544 ms 28940 KB ans=YES N=65421
87 Correct 601 ms 32440 KB ans=YES N=68351
88 Correct 402 ms 26548 KB ans=YES N=67027
89 Correct 671 ms 44244 KB ans=YES N=68879
90 Correct 601 ms 33200 KB ans=YES N=67256
91 Correct 1271 ms 60772 KB ans=YES N=148315
92 Correct 1620 ms 273464 KB ans=NO N=142745
93 Correct 1755 ms 324140 KB ans=NO N=148443
94 Correct 1072 ms 57932 KB ans=YES N=148328
95 Correct 1095 ms 58208 KB ans=YES N=147855
96 Correct 1100 ms 58432 KB ans=YES N=150000
97 Correct 1068 ms 57048 KB ans=YES N=144725
98 Correct 1098 ms 58252 KB ans=YES N=149445
99 Correct 1113 ms 57500 KB ans=YES N=144455
100 Correct 1077 ms 57096 KB ans=YES N=143487
101 Correct 1178 ms 59428 KB ans=YES N=149688
102 Correct 2188 ms 105988 KB ans=YES N=141481
103 Correct 2592 ms 150816 KB ans=YES N=147430
104 Correct 1948 ms 84104 KB ans=YES N=142247
105 Correct 2236 ms 101736 KB ans=YES N=149941
106 Correct 2407 ms 141064 KB ans=YES N=141635
107 Correct 2782 ms 130192 KB ans=YES N=142896
108 Correct 2489 ms 144680 KB ans=YES N=142069
109 Correct 1773 ms 67780 KB ans=YES N=142378
110 Correct 1891 ms 114340 KB ans=YES N=150000
111 Correct 2484 ms 165936 KB ans=YES N=141452
112 Correct 2110 ms 158500 KB ans=YES N=134453
113 Correct 2288 ms 164840 KB ans=YES N=144172

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 32004 KB ans=NO N=66151
2 Correct 639 ms 111656 KB ans=NO N=64333
3 Correct 397 ms 27464 KB ans=YES N=69316
4 Correct 368 ms 26612 KB ans=YES N=66695
5 Correct 423 ms 27416 KB ans=YES N=68436
6 Correct 437 ms 28072 KB ans=YES N=70000
7 Correct 439 ms 27920 KB ans=YES N=68501
8 Correct 502 ms 29188 KB ans=YES N=70000
9 Correct 605 ms 30768 KB ans=YES N=65009
10 Correct 905 ms 48920 KB ans=YES N=67007
11 Correct 990 ms 56556 KB ans=YES N=66357
12 Correct 1008 ms 62432 KB ans=YES N=65430
13 Correct 977 ms 60372 KB ans=YES N=65790
14 Correct 962 ms 56292 KB ans=YES N=66020
15 Correct 921 ms 51920 KB ans=YES N=65809
16 Correct 709 ms 35788 KB ans=YES N=65651
17 Correct 1190 ms 78116 KB ans=YES N=68040
18 Correct 1022 ms 68616 KB ans=YES N=66570
19 Correct 536 ms 29088 KB ans=YES N=65421
20 Correct 589 ms 32428 KB ans=YES N=68351
21 Correct 379 ms 26488 KB ans=YES N=67027
22 Correct 586 ms 44188 KB ans=YES N=68879
23 Correct 583 ms 33444 KB ans=YES N=67256

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4600 KB ans=NO N=1934
2 Correct 8 ms 1872 KB ans=NO N=1965
3 Correct 10 ms 1116 KB ans=YES N=1824
4 Correct 11 ms 1272 KB ans=YES N=1981
5 Correct 12 ms 1144 KB ans=YES N=1814
6 Correct 12 ms 1272 KB ans=YES N=1854
7 Correct 10 ms 1144 KB ans=YES N=1831
8 Correct 12 ms 1276 KB ans=YES N=2000
9 Correct 14 ms 1500 KB ans=YES N=1847
10 Correct 13 ms 1528 KB ans=YES N=1819
11 Correct 10 ms 1272 KB ans=YES N=1986
12 Correct 16 ms 1912 KB ans=YES N=2000
13 Correct 15 ms 2168 KB ans=YES N=1834
14 Correct 16 ms 2040 KB ans=YES N=1860
15 Correct 16 ms 2168 KB ans=YES N=1898
16 Correct 14 ms 1756 KB ans=YES N=1832
17 Correct 15 ms 2552 KB ans=YES N=1929
18 Correct 13 ms 1376 KB ans=YES N=1919
19 Correct 15 ms 2040 KB ans=YES N=1882
20 Correct 15 ms 2552 KB ans=YES N=1922
21 Correct 11 ms 1528 KB ans=YES N=1989
22 Correct 10 ms 1784 KB ans=YES N=1978
23 Correct 11 ms 1912 KB ans=YES N=1867
24 Correct 357 ms 32004 KB ans=NO N=66151
25 Correct 639 ms 111656 KB ans=NO N=64333
26 Correct 397 ms 27464 KB ans=YES N=69316
27 Correct 368 ms 26612 KB ans=YES N=66695
28 Correct 423 ms 27416 KB ans=YES N=68436
29 Correct 437 ms 28072 KB ans=YES N=70000
30 Correct 439 ms 27920 KB ans=YES N=68501
31 Correct 502 ms 29188 KB ans=YES N=70000
32 Correct 605 ms 30768 KB ans=YES N=65009
33 Correct 905 ms 48920 KB ans=YES N=67007
34 Correct 990 ms 56556 KB ans=YES N=66357
35 Correct 1008 ms 62432 KB ans=YES N=65430
36 Correct 977 ms 60372 KB ans=YES N=65790
37 Correct 962 ms 56292 KB ans=YES N=66020
38 Correct 921 ms 51920 KB ans=YES N=65809
39 Correct 709 ms 35788 KB ans=YES N=65651
40 Correct 1190 ms 78116 KB ans=YES N=68040
41 Correct 1022 ms 68616 KB ans=YES N=66570
42 Correct 536 ms 29088 KB ans=YES N=65421
43 Correct 589 ms 32428 KB ans=YES N=68351
44 Correct 379 ms 26488 KB ans=YES N=67027
45 Correct 586 ms 44188 KB ans=YES N=68879
46 Correct 583 ms 33444 KB ans=YES N=67256
47 Correct 1227 ms 60864 KB ans=YES N=148315
48 Correct 1602 ms 273496 KB ans=NO N=142745
49 Correct 1748 ms 323980 KB ans=NO N=148443
50 Correct 1042 ms 57928 KB ans=YES N=148328
51 Correct 1053 ms 58148 KB ans=YES N=147855
52 Correct 1039 ms 58408 KB ans=YES N=150000
53 Correct 1018 ms 56920 KB ans=YES N=144725
54 Correct 1103 ms 58228 KB ans=YES N=149445
55 Correct 1082 ms 57528 KB ans=YES N=144455
56 Correct 1099 ms 57012 KB ans=YES N=143487
57 Correct 1277 ms 59360 KB ans=YES N=149688
58 Correct 2207 ms 105892 KB ans=YES N=141481
59 Correct 2529 ms 150896 KB ans=YES N=147430
60 Correct 1947 ms 84180 KB ans=YES N=142247
61 Correct 2213 ms 101888 KB ans=YES N=149941
62 Correct 2432 ms 141200 KB ans=YES N=141635
63 Correct 2408 ms 130000 KB ans=YES N=142896
64 Correct 2508 ms 144640 KB ans=YES N=142069
65 Correct 1514 ms 67820 KB ans=YES N=142378
66 Correct 1898 ms 114216 KB ans=YES N=150000
67 Correct 2402 ms 166100 KB ans=YES N=141452
68 Correct 2126 ms 158420 KB ans=YES N=134453
69 Correct 2365 ms 164924 KB ans=YES N=144172