Submission #644457

#	Time	Username	Problem	Language	Result	Execution time	Memory
644457		Cyanmond	Alternating Current (BOI18_alternating)	C++17	0 / 100	253 ms	27380 KiB

alternating

#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;
    }

    // solve
    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);
    }

    // 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 ? 0 : 1);
        }
        std::cout << std::endl;
    }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26