Submission #987556

#TimeUsernameProblemLanguageResultExecution timeMemory
987556PurpleCrayonAlternating Current (BOI18_alternating)C++17
100 / 100
101 ms16540 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 1e5+10, MOD = 1e9+7; void no() { cout << "impossible\n"; } int ans[N]; vector<int> adj[N]; bool dfs(int c, int b) { ans[c] = b; for (int nxt : adj[c]) { if (ans[nxt] == -1) { if (!dfs(nxt, b ^ 1)) return false; } else if (ans[nxt] == b) return false; } return true; } void solve() { int n, m; cin >> n >> m; vector<pair<int, int>> v(m); for (int i = 0; i < m; i++) adj[i].clear(); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b, --a, --b; v[i] = {a, b}; } vector<int> cnt(n); auto add = [&](int l, int r) { cnt[l]++; if (r < n-1) cnt[r+1]--; }; for (auto [l, r] : v) { if (l <= r) { add(l, r); } else { add(l, n-1); add(0, r); } } for (int i = 1; i < n; i++) cnt[i] += cnt[i-1]; if (*min_element(cnt.begin(), cnt.end()) < 2) { no(); return; } vector<int> use; for (int i = 0; i < n; i++) { if (cnt[i] == 2) { use.push_back(i); } } fill(ans, ans + m, -1); bool done_no = 0; auto solve_hard = [&]() { auto get_nxt = [&](int i) { int idx = lower_bound(use.begin(), use.end(), i) - use.begin(); if (idx == sz(use)) return use[0]; return use[idx]; }; // cerr << "use: "; // for (int x : use) cerr << x << ' '; // cerr << endl; vector<vector<int>> mine(n); for (int i = 0; i < m; i++) { auto [l, r] = v[i]; // cerr << "> " << l << ' ' << r << endl; set<int> mark; if (l <= r) { int c = get_nxt(l); while (!mark.count(c) && l <= c && c <= r) { // cerr << c << ' '; mark.insert(c); c = get_nxt((c + 1) % n); } // cerr << endl << endl; } else { int c = get_nxt(l); while (!mark.count(c) && (c >= l || c <= r)) { // cerr << c << ' '; mark.insert(c); c = get_nxt((c + 1) % n); } // cerr << endl << endl; } for (int x : mark) { mine[x].push_back(i); } } for (int x : use) { assert(sz(mine[x]) == 2); int one = mine[x][0], two = mine[x][1]; // cerr << "> " << one << ' ' << two << endl; adj[one].push_back(two); adj[two].push_back(one); } for (int i = 0; i < m; i++) if (sz(adj[i]) && ans[i] == -1) { if (!dfs(i, 0)) { no(); done_no = 1; return; } } }; if (sz(use)) solve_hard(); if (done_no) return; vector<int> one; for (int i = 0; i < m; i++) { if (ans[i] == 0 || ans[i] == -1) { one.push_back(i); } } auto reduce = [&]() { // clean one pair<int, int> big{-1, -1}; vector<vector<int>> who(n); for (int x : one) { auto [l, r] = v[x]; who[l].push_back(x); if (l <= r) { big = max(big, make_pair(r - l + 1, x)); } else { big = max(big, make_pair(n - (l - r - 1), x)); } } int start = v[big.second].first; auto dist = [&](int x) { return (x + n - start) % n; }; vector<pair<int, int>> fake_v = v; for (auto& [l, r] : fake_v) { if (dist(r) < dist(l)) { r = (start + n - 1) % n; } } int p = (start + 1) % n; int last = big.second; vector<int> new_one; new_one.push_back(last); while (true) { pair<int, int> best{-1, -1}; while (p != start && dist(p) <= dist(fake_v[last].second) + 1) { for (int x : who[p]) { auto [l, r] = fake_v[x]; best = max(best, make_pair(dist(r), x)); } p = (p + 1) % n; } // cerr << "> " << last << ' ' << p << ' ' << best.second << endl; if (best.second == -1 || dist(fake_v[best.second].second) <= dist(fake_v[last].second)) break; last = best.second; new_one.push_back(last); } swap(one, new_one); }; /* for (int x : one) cerr << x << ' '; cerr << endl; */ reduce(); /* for (int x : one) cerr << x << ' '; cerr << endl; */ for (int x : one) { ans[x] = 0; } vector<int> two; for (int i = 0; i < m; i++) { if (ans[i] != 0) { ans[i] = 1; two.push_back(i); } } auto good = [&](vector<int> idx) { // check vector<int> cnt_check(n); auto add_check = [&](int l, int r) { cnt_check[l]++; if (r < n-1) cnt_check[r+1]--; }; for (int x : idx) { auto [l, r] = v[x]; if (l <= r) { add_check(l, r); } else { add_check(l, n-1); add_check(0, r); } } for (int i = 1; i < n; i++) cnt_check[i] += cnt_check[i-1]; return *min_element(cnt_check.begin(), cnt_check.end()) > 0; }; if (!good(one) || !good(two)) { no(); return; } for (int i = 0; i < m; i++) cout << ans[i]; cout << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#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...