Submission #987550

#TimeUsernameProblemLanguageResultExecution timeMemory
987550PurpleCrayonAlternating Current (BOI18_alternating)C++17
0 / 100
16 ms9436 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"; exit(0); } int ans[N]; vector<int> adj[N]; void dfs(int c, int b) { ans[c] = b; for (int nxt : adj[c]) { if (ans[nxt] == -1) dfs(nxt, b ^ 1); else if (ans[nxt] == b) no(); } } void solve() { int n, m; cin >> n >> m; vector<pair<int, int>> v(m); 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(); } vector<int> use; for (int i = 0; i < n; i++) { if (cnt[i] == 2) { use.push_back(i); } } memset(ans, -1, sizeof(ans)); 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) { dfs(i, 0); } }; if (sz(use)) solve_hard(); 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 vector<vector<ar<int, 3>>> ev(2 * n); for (int x : one) { auto [l, r] = v[x]; if ((r + 1) % n == l) { one = {x}; break; } if (l <= r) { ev[l].push_back({x, +1, r}); ev[r].push_back({x, -1, l}); ev[l + n].push_back({x, +1, r + n}); ev[r + n].push_back({x, -1, l + n}); } else { ev[l].push_back({x, +1, r + n}); ev[r + n].push_back({x, -1, l}); } } set<int> bad; set<pair<int, int>> open; for (int i = 0; i < 2 * n; i++) { // cerr << "at: " << i << endl; for (auto [c, t, opp] : ev[i]) { if (t == +1) { open.emplace(i, c); // cerr << "add: " << c << endl; } } for (auto [c, t, opp] : ev[i]) { if (t == -1) { auto it = open.find({opp, c}); if (it != open.begin()) { // cerr << "mark: " << c << endl; bad.insert(c); } } } for (auto [c, t, opp] : ev[i]) { if (t == -1) { // cerr << "remove: " << c << endl; open.erase({opp, c}); } } } vector<int> new_one; for (int x : one) if (!bad.count(x)) new_one.push_back(x); 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(); cout << "yes\n"; 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...