Submission #1149519

#TimeUsernameProblemLanguageResultExecution timeMemory
1149519LucaLucaMAlternating Current (BOI18_alternating)C++20
0 / 100
2220 ms1114112 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <random> #include <set> using ll = long long; #define debug(x) #x << " = " << x << '\n' const int NMAX = 1000; std::vector<int> g[NMAX]; bool vis[NMAX]; bool color[NMAX]; void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } bool bipartite = true; void dfs(int u) { vis[u] = true; for (const auto &v : g[u]) { if (!vis[v]) { color[v] = 1 ^ color[u]; dfs(v); } else { if (color[u] == color[v]) { bipartite = false; } } } } std::mt19937 rng(123); int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n, m; std::cin >> n >> m; std::vector<std::pair<int, int>> a(m); for (auto &[l, r] : a) { std::cin >> l >> r; l--, r--; } std::vector<std::vector<int>> active(n); for (int i = 0; i < m; i++) { auto [l, r] = a[i]; if (l <= r) { for (int j = l; j <= r; j++) { active[j].push_back(i); } } else { for (int j = l; j < n; j++) { active[j].push_back(i); } for (int j = 0; j <= r; j++) { active[j].push_back(i); } } } for (int i = 0; i < n; i++) { if ((int) active[i].size() <= 1) { std::cout << "impossible"; return 0; } else if ((int) active[i].size() == 2) { add_edge(active[i][0], active[i][1]); } } for (int i = 0; i < m; i++) { if (!vis[i] && !g[i].empty()) { dfs(i); } } if (!bipartite) { std::cout << "impossible"; } else { std::vector<int> order(m); for (int i = 0; i < m; i++) { order[i] = i; } for (int repeat = 0; repeat < 1; repeat++) { std::vector<int> taken(n, 0); std::set<int> st[2]; auto add_colored = [&](int l, int r, int c) { if (l <= r) { for (int i = l; i <= r; i++) { taken[i] |= (1 << c); } } else { for (int i = l; i < n; i++) { taken[i] |= (1 << c); } for (int i = 0; i <= r; i++) { taken[i] |= (1 << c); } } }; // std::shuffle(order.begin(), order.end(), rng); for (int i = 0; i < m; i++) { if (vis[i]) { std::cout << debug(i); add_colored(a[i].first, a[i].second, color[i]); } } for (const auto &i : order) { if (!vis[i]) { auto [l, r] = a[i]; int become = 0; if (l <= r) { for (int j = l; j <= r; j++) { become |= (3 ^ taken[j]); } } else { for (int j = l; j < n; j++) { become |= (3 ^ taken[j]); } for (int j = 0; j <= r; j++) { become |= (3 ^ taken[j]); } } if (become & 1) { color[i] = 0; } else { color[i] = 1; } add_colored(l, r, color[i]); } } for (int i = 0; i < m; i++) { std::cout << color[i]; } return 0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...