oj.uz

Submission #644456

# Submission time Handle Problem Language Result Execution time Memory
644456 2022-09-24T17:11:50 Z Cyanmond Alternating Current (BOI18_alternating) C++17
0 / 100
 232 ms 28664 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;
    }

    if (K % 2 == 0) {
        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, int i) {
            auto itr = s.lower_bound(A[i]);
            while (itr != s.end() and *itr < B[i]) {
                itr = s.erase(itr);
            }
            if (B[i] <= N) {
                return;
            }
            itr = s.begin();
            while (itr != s.end() and *itr < B[i] - N) {
                itr = s.erase(itr);
            }            
        };

        for (int i = 0; i < M; ++i) {
            if (root[i] == i) {
                const bool is_x = reorder[i] % 2 == 0;
                auto &s = is_x ? bad_x : bad_y;
                fill(s, i);
            } else {
                const bool is_x = reorder[root[i]] % 2 == 1;
                auto &s = is_x ? bad_x : bad_y;
                fill(s, i);
            }
        }

        const bool answer = bad_x.empty() and bad_y.empty();
        if (answer) {
            for (int i = 0; i < M; ++i) {
                if (root[i] == i) {
                    const bool is_x = reorder[i] % 2 == 0;
                    std::cout << is_x;
                } else {
                    const bool is_x = reorder[root[i]] % 2 == 1;
                    std::cout << is_x;
                }
            }
            std::cout << std::endl;
        } else {
            std::cout << "impossible" << std::endl;
        }
    } else {
        auto calc_time = [&](const std::vector<int> roots,
                                const std::vector<std::vector<int>> od) {
            std::vector<int> time_x(N, M), time_y(N, M);
            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);
                }
                if (B[i] <= N) {
                    return;
                }
                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_x2, time_y2] = calc_time(roots, od);
        for (auto &e : time_x2) {
            e = K - e;
        }
        for (auto &e : time_y2) {
            e = K - e;
        }

        std::set<int> ok_pos;
        for (int i = 0; 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];
                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);
        }

        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 ? 0 : 1);
            }
            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 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB 'impossible' claimed, but there is a solution
5 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 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB 'impossible' claimed, but there is a solution
5 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 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 18124 KB Output is correct
2 Correct 50 ms 14764 KB Output is correct
3 Correct 125 ms 21052 KB Output is correct
4 Correct 80 ms 19116 KB Output is correct
5 Correct 217 ms 27912 KB Output is correct
6 Correct 214 ms 26856 KB Output is correct
7 Correct 176 ms 22092 KB Output is correct
8 Correct 96 ms 16568 KB Output is correct
9 Correct 48 ms 14132 KB Output is correct
10 Correct 232 ms 28664 KB Output is correct
11 Correct 152 ms 20588 KB Output is correct
12 Correct 168 ms 22492 KB Output is correct
13 Correct 47 ms 14672 KB Output is correct
14 Correct 96 ms 16232 KB Output is correct
15 Correct 219 ms 23072 KB Output is correct
16 Correct 146 ms 23320 KB Output is correct
17 Correct 133 ms 20788 KB Output is correct
18 Runtime error 60 ms 7220 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 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -