Submission #397758

#	Time	Username	Problem	Language	Result	Execution time	Memory
397758		KoD	Alternating Current (BOI18_alternating)	C++17	32 / 100	79 ms	7624 KiB

alternating

#include <bits/stdc++.h>

using ll = long long;

template <class T>
using Vec = std::vector<T>;
  
int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        A[i] -= 1;
        B[i] -= 1;
    }
    if (N <= 15 and M <= 15) {
        for (int set = 0; set < (1 << M); ++set) {
            bool ok = true;
            for (int i = 0; i < N; ++i) {
                bool f = false, g = false;
                for (int j = 0; j < M; ++j) {
                    if ((A[j] <= B[j] and A[j] <= i and i <= B[j]) or (A[j] > B[j] and (A[j] <= i or i <= B[j]))) {
                        ((set >> j & 1) ? f : g) = true;
                    }
                }
                if (!f or !g) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                for (int j = 0; j < M; ++j) {
                    std::cout << (set >> j & 1);
                }
                std::cout << '\n';
                return 0;
            }
        }
        std::cout << "impossible\n";
        return 0;
    }
    Vec<Vec<int>> right(N);
    for (int i = 0; i < M; ++i) {
        assert(A[i] <= B[i]);
        right[A[i]].push_back(i);
    }
    int r1 = 0, r2 = 0;
    Vec<int> assign(M);
    for (int i = 0; i < N; ++i) {
        if (std::min(r1, r2) < i) {
            std::cout << "impossible\n";
            return 0;
        }
        for (const auto x: right[i]) {
            if (r1 < r2) {
                assign[x] = 0;
                r1 = std::max(r1, B[x] + 1);
            }
            else {
                assign[x] = 1;
                r2 = std::max(r2, B[x] + 1);
            }
        }
    }
    if (std::min(r1, r2) < N) {
        std::cout << "impossible\n";
    }
    else {
        for (const auto x: assign) {
            std::cout << x;
        }
        std::cout << '\n';
    }
    return 0;
}

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