Submission #1260556

#TimeUsernameProblemLanguageResultExecution timeMemory
1260556niepamietamhaslaAlternating Current (BOI18_alternating)C++20
0 / 100
26 ms9144 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> typedef long long ll; const int MAXN = 1e5 + 5; struct d{ int a; int b; int nr; int org; }; int ans[MAXN]; vector<d> dzieci[MAXN]; int P[MAXN]; vector<d> przedzialy; bool comp(const d &d1, const d &d2){ if(d1.a != d2.a) return d1.a < d2.a; return false; } vector<d> wejscie; int n, m; int pref[MAXN][2]; int G[MAXN]; int G2[MAXN]; bool comp2(const d &d1, const d &d2){ int s1; if(d1.a <= d1.b) s1 = d1.b - d1.a + 1; else s1 = n - d1.a + 1 + d1.b; int s2; if(d2.a <= d2.b) s2 = d2.b - d2.a + 1; else s2 = n - d2.a + 1 + d2.b; if(s1 != s2){ return s1 > s2; } return false; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cout << n << " " << m << "\n"; int a, b; for(int i = 1; i <= m; ++i){ ans[i] = -1; cin >> a >> b; cout << a << " " << b << "\n"; if(a > b){ G[a]++; G[1]++; G[b+1]--; } else{ G[a]++; G[b+1]--; } przedzialy.push_back({a, b, i, i}); } for(int i = 1; i <= n; ++i){ G[i] += G[i-1]; if(G[i] <= 1){ cout << "impossible\n"; return 0; } } sort(przedzialy.begin(), przedzialy.end(), comp2); int cnt = 1; for(auto &u : przedzialy){ //cout << u.a << " " << u.b << " LK\n"; u.nr = cnt; cnt++; } set<pii> duze; for(auto u : przedzialy){ // cout << u.a << " " << u.b << " " << u.nr << " po kolei\n"; int p = -1; auto it = duze.lower_bound({u.a, 1e9}); if(it != duze.begin()){ //cout << it->first << " " << it->second << " curr\n"; p = (*(--it)).second; } else{ if(duze.size() != 0) p = (*(--duze.end())).second; } //cout << p << " P\n";\ P[u.nr] = p; if(p == -1){ duze.insert({u.a, u.nr}); } else{ if(u.a <= u.b){ if(przedzialy[p-1].a <= przedzialy[p-1].b){ if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr}); else dzieci[p].push_back(u); } else{ if(!(przedzialy[p-1].a <= u.a or przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr}); else dzieci[p].push_back(u); } } else{ if(przedzialy[p-1].a <= przedzialy[p-1].b){ duze.insert({u.a, u.nr}); } else{ if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b) and przedzialy[p-1 ].a != (przedzialy[p-1].b+1)%n){ duze.insert({u.a, u.nr}); } else{ dzieci[p].push_back(u); } } } } } vector<d> tmp; for(auto u : duze){ //cout << u.first << " " << u.second << " duze\n"; tmp.push_back(przedzialy[u.second-1]); } przedzialy = tmp; sort(przedzialy.begin(), przedzialy.end(), comp); // for(auto u : przedzialy){ // cout << u.a << " " << u.b << " U\n"; // } // return 0; if(przedzialy.size() % 2 == 0){ for(int i = 0; i < przedzialy.size(); ++i){ int ktory = (i % 2); if(przedzialy[i].a > przedzialy[i].b){ pref[przedzialy[i].a][ktory]++; pref[1][ktory]++; pref[przedzialy[i].b+1][ktory]--; } else{ pref[przedzialy[i].a][ktory]++; pref[przedzialy[i].b+1][ktory]--; } ans[przedzialy[i].org] = ktory; ktory ^= 1; for(auto u : dzieci[przedzialy[i].nr]){ if(u.a > u.b){ pref[u.a][ktory]++; pref[1][ktory]++; pref[u.b+1][ktory]--; } else{ pref[u.a][ktory]++; pref[u.b+1][ktory]--; } ans[u.org] = ktory; } } bool c = true; for(int i = 1; i <= n; ++i){ for(int j = 0; j < 2; ++j){ pref[i][j] += pref[i-1][j]; if(pref[i][j] <= 0) c = false; } } if(c){ for(int i = 1; i <= m; ++i){ cout << ans[i]; } cout << "\n"; } else{ cout << "impossible\n"; } } else{ if(przedzialy.size() == 1){ auto u = przedzialy[0]; int ktory = 0; if(u.a > u.b){ pref[u.a][ktory]++; pref[1][ktory]++; pref[u.b+1][ktory]--; } else{ pref[u.a][ktory]++; pref[u.b+1][ktory]--; } ans[u.org] = ktory; ktory ^= 1; for(auto y : dzieci[u.nr]){ if(y.a > y.b){ pref[y.a][ktory]++; pref[1][ktory]++; pref[y.b+1][ktory]--; } else{ pref[y.a][ktory]++; pref[y.b+1][ktory]--; } ans[y.org] = ktory; } bool c = true; for(int i = 1; i <= n; ++i){ for(int j = 0; j < 2; ++j){ pref[i][j] += pref[i-1][j]; if(pref[i][j] <= 0) c = false; } } if(c){ for(int i = 1; i <= m; ++i){ cout << ans[i]; } cout << "\n"; } else{ cout << "impossible\n"; } return 0; } for(int i = 1; i <= n; ++i){ if(G[i] > 2) G2[i]++; G2[i] += G2[i-1]; } int sajz = przedzialy.size(); for(int i = 0; i < sajz; ++i){ int nxt = (i == sajz - 1 ? 0 : i+1); auto u = przedzialy[i]; auto v = przedzialy[nxt]; //cout << u.a << " " << u.b << " U\n"; auto intersect = [=](d A, d B) -> vector<pii>{ if(A.a <= A.b and B.a <= B.b){ //cout << "#\n"; if(A.b >= B.a) return {{B.a, A.b}}; else return {}; } else if(A.a > A.b and B.a > B.b){ //cout << "$\n"; vector<pii> D; D = {{max(A.a, B.a), n}, {1, min(A.b, B.b)}}; if(A.b >= B.a){ D.push_back({B.a, A.b}); } return D; } else if(A.a <= A.b and B.a > B.b){ //cout << "^\n"; if(A.b >= B.a and B.b >= A.a){ return {{B.a, A.b}, {A.a, B.b}}; } else if(A.b >= B.a){ return {{B.a, A.b}}; } else if(B.b >= A.a){ return {{A.a, B.b}}; } else{ return {}; } } else{ //cout << "&\n"; swap(A, B); if(A.b >= B.a and B.b >= A.a){ return {{B.a, A.b}, {A.a, B.b}}; } else if(A.b >= B.a){ return {{B.a, A.b}}; } else if(B.b >= A.a){ return {{A.a, B.b}}; } else{ return {}; } } }; vector<pii> C = intersect(u, v); //cout << i << " i\n"; // for(auto u : C){ // cout << u.first << " " << u.second << " pr\n"; // } bool c = true; for(auto x : C){ //cout << x.first << " " << x.second << "X\n"; //cout << G2[x.second] - G2[x.first - 1] << " " << x.second - x.first + 1 << " por\n"; if(G2[x.second] - G2[x.first - 1] != x.second - x.first + 1){ c = false; } } if(c){ //cout << i << " i\n"; //cout << "#\n"; ans[przedzialy[i].org] = 0; ans[przedzialy[nxt].org] = 0; for(auto u : dzieci[przedzialy[i].nr]){ ans[u.org] = ans[przedzialy[i].org] ^ 1; } for(auto u : dzieci[przedzialy[nxt].nr]){ ans[u.org] = ans[przedzialy[nxt].org] ^ 1; } if(nxt == 0){ //cout << "$\n"; for(int j = nxt + 1; j < i; ++j){ ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1; for(auto u : dzieci[przedzialy[j].nr]){ ans[u.org] = ans[przedzialy[j].org] ^ 1; } } for(int j = 1; j <= m; ++j){ cout << ans[j]; } cout << "\n"; return 0; } else{ for(int j = i - 1; j >= 0; --j){ ans[przedzialy[j].org] = ans[przedzialy[j + 1].org] ^ 1; //cout << przedzialy[j].a << " " << przedzialy[j].b << " ab1\n"; for(auto u : dzieci[przedzialy[j].nr]){ //cout << u.a << " " << u.b << " syn1\n"; ans[u.org] = ans[przedzialy[j].org] ^ 1; } } for(int j = nxt + 1; j < sajz; ++j){ ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1; //cout << przedzialy[j].a << " " << przedzialy[j].b << " ab2\n"; for(auto u : dzieci[przedzialy[j].nr]){ //cout << u.a << " " << u.b << " syn2\n"; ans[u.org] = ans[przedzialy[j].org] ^ 1; } } for(int j = 1; j <= m; ++j){ cout << ans[j]; } cout << "\n"; return 0; } } } cout << "impossible\n"; } 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...