oj.uz

Submission #644595

# Submission time Handle Problem Language Result Execution time Memory
644595 2022-09-25T03:39:51 Z Cyanmond Alternating Current (BOI18_alternating) C++17
0 / 100
 265 ms 27776 KB 
#include <bits/stdc++.h>

int main() {
    // input
    int N, M;
    std::cin >> N >> M;
    
    std::vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i];
        if (A[i] >= B[i]) {
            B[i] += N;
        }
    }
    
    // calc root
    std::vector<int> root(M, -1);

    std::vector<std::vector<int>> in(2 * N);
    for (int i = 0; i < M; ++i) {
        in[A[i]].push_back(i);
        in[A[i] + N].push_back(i);
    }

    std::pair<int, int> max_right = {-1, 0};
    for (int i = 0; i < 2 * N; ++i) {
        // reverse-sort
        std::sort(in[i].begin(), in[i].end(), [&](const int a, const int b) {
            int r1 = B[a], r2 = B[b];
            while (r1 <= i) {
                r1 += N;
            }
            while (r2 <= i) {
                r2 += N;
            }
            return r1 > r2;
        });

        for (const int e : in[i]) {
            int l = i, r = B[e];
            while (r <= l) {
                r += N;
            }

            if (r < max_right.first) {
                root[e] = max_right.second;
            } else {
                max_right.first = r;
                max_right.second = e;
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        auto rec = [&](auto &&self, const int v) {
            if (root[v] == -1) {
                return v;
            } else {
                return root[v] = self(self, root[v]);
            }
        };
        rec(rec, i);
    }

    std::vector<int> roots;
    for (int i = 0; i < M; ++i) {
        if (root[i] == -1) {
            roots.push_back(root[i] = i);
        }
    }
    std::sort(roots.begin(), roots.end(), [&](const int a, const int b) {
        return A[a] < A[b];
    });
    
    const int K = (int)roots.size();
    std::vector<int> reorder(N, -1);
    for (int i = 0; i < K; ++i) {
        reorder[roots[i]] = i;
    }

    // calc limit
    auto calc_time = [&](const std::vector<int> roots,
                            const std::vector<std::vector<int>> od) {
        std::vector<int> time_x(N, K), time_y(N, K);
        std::set<int> bad_x, bad_y;
        for (int i = 0; i < N; ++i) {
            bad_x.insert(i);
            bad_y.insert(i);
        }

        auto fill = [&](std::set<int> &s, std::vector<int> &tiv, const int i, const int t) {
            auto itr = s.lower_bound(A[i]);
            while (itr != s.end() and *itr < B[i]) {
                tiv[*itr] = t;
                itr = s.erase(itr);
            }

            itr = s.begin();
            while (itr != s.end() and *itr < B[i] - N) {
                tiv[*itr] = t;
                itr = s.erase(itr);
            }            
        };


        for (int i = 0; i < K; ++i) {
            const bool is_x = i % 2 == 0;
            fill(is_x ? bad_x : bad_y, is_x ? time_x : time_y, roots[i], i);
            for (const int e : od[i]) {
                fill(is_x ? bad_y : bad_x, is_x ? time_y : time_x, e, i);
            }
        }

        return std::make_pair(time_x, time_y);
    };
    
    std::vector<std::vector<int>> od(K);
    for (int i = 0; i < M; ++i) {
        if (root[i] == i) {
            continue;
        }
        od[reorder[root[i]]].push_back(i);
    }

    const auto [time_x1, time_y1] = calc_time(roots, od);
    std::reverse(roots.begin(), roots.end());
    std::reverse(od.begin(), od.end());
    auto [time_y2, time_x2] = calc_time(roots, od);
    for (auto &e : time_x2) {
        e = K - e;
    }
    for (auto &e : time_y2) {
        e = K - e;
    }

    // skip
    int ma = -1;
    for (const int e : time_x1) {
        ma = std::max(ma, e);
    }
    for (const int e : time_y1) {
        ma = std::max(ma, e);
    }
    if (ma != K) {
        for (int i = 0; i < M; ++i) {
            bool answer = root[i] == i;
            answer ^= reorder[root[i]] % 2 == 1;
            std::cout << answer;
        }
        std::cout << std::endl;
        return 0;
    }

    // solve
    std::set<int> ok_pos;
    for (int i = 1; i < K; ++i) {
        ok_pos.insert(i);
    }

    for (int i = 0; i < N; ++i) {
        auto erase = [&](const std::vector<int> &t1, const std::vector<int> &t2) {
            const int l = t2[i], r = t1[i] + 1;
            auto itr = ok_pos.lower_bound(l);
            while (itr != ok_pos.end() and *itr < r) {
                itr = ok_pos.erase(itr);
            }
        };

        erase(time_x1, time_x2);
        erase(time_y1, time_y2);
    }

    // output
    if (ok_pos.empty()) {
        std::cout << "impossible" << std::endl;
    } else {
        const int p = *ok_pos.begin();
        for (int i = 0; i < M; ++i) {
            bool answer = root[i] == i;
            answer ^= reorder[root[i]] >= p;
            answer ^= reorder[root[i]] % 2 == 1;
            std::cout << answer;
        }
        std::cout << std::endl;
    }
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 216 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Runtime error 1 ms 340 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 216 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Runtime error 1 ms 340 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 216 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Runtime error 1 ms 340 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 23788 KB Output is correct
2 Correct 93 ms 16324 KB Output is correct
3 Correct 123 ms 20328 KB Output is correct
4 Correct 125 ms 20448 KB Output is correct
5 Correct 206 ms 26920 KB Output is correct
6 Correct 206 ms 25604 KB Output is correct
7 Correct 197 ms 25056 KB Output is correct
8 Correct 95 ms 16636 KB Output is correct
9 Correct 89 ms 15548 KB Output is correct
10 Correct 208 ms 27776 KB Output is correct
11 Correct 185 ms 24348 KB Output is correct
12 Correct 244 ms 24228 KB Output is correct
13 Correct 109 ms 16280 KB Output is correct
14 Correct 107 ms 16284 KB Output is correct
15 Correct 265 ms 22428 KB Output is correct
16 Correct 151 ms 23268 KB Output is correct
17 Correct 183 ms 22416 KB Output is correct
18 Runtime error 59 ms 6772 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 216 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Runtime error 1 ms 340 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -