Submission #1259896

#TimeUsernameProblemLanguageResultExecution timeMemory
1259896Zbyszek99Alternating Current (BOI18_alternating)C++20
19 / 100
45 ms6612 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; int n,m; int rel_ind[100001]; bool ans[100001]; int parent[100001]; int sum[100001]; int tri_sum[100001]; vector<pii> segs; vi big; vi rest; bool comp(pair<int,pii> a, pair<int,pii> b) { return (a.ss.ss-a.ss.ff+m)%m > (b.ss.ss-b.ss.ff+m)%m; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> m >> n; vector<pair<int,pii>> segs2; rep(i,n) { int a,b; cin >> a >> b; a--; b--; segs2.pb({i,{a,b}}); } sort(all(segs2),comp); rep(i,siz(segs2)) { rel_ind[i] = segs2[i].ff; segs.pb(segs2[i].ss); } set<pii> big_segs; int ind = 0; vi rest; forall(it,segs) { int prv = -1; auto ptr= big_segs.lower_bound({it.ff,1e9}); if(ptr != big_segs.begin()) { prv = (*(--ptr)).ss; } else { if(siz(big_segs) != 0) prv = (*(--big_segs.end())).ss; } parent[ind] = prv; if(prv == -1) big_segs.insert({it.ff,ind}); else { if(it.ff <= it.ss) { if(segs[prv].ff <= segs[prv].ss) { if(!(segs[prv].ff <= it.ff && segs[prv].ss >= it.ss)) big_segs.insert({it.ff,ind}); else rest.pb(ind); } else { if(!(segs[prv].ff <= it.ff || segs[prv].ss >= it.ss)) big_segs.insert({it.ff,ind}); else rest.pb(ind); } } else { if(segs[prv].ff <= segs[prv].ss) { big_segs.insert({it.ff,ind}); } else { if(!(segs[prv].ff <= it.ff && segs[prv].ss >= it.ss) && segs[prv].ff != (segs[prv].ss+1)%m) big_segs.insert({it.ff,ind}); else rest.pb(ind); } } } ind++; } rep(i,n) { if(segs[i].ff <= segs[i].ss) { sum[segs[i].ff]++; sum[segs[i].ss+1]--; } else { sum[0]++; sum[segs[i].ss+1]--; sum[segs[i].ff]++; } } vi big; forall(it,big_segs) big.pb(it.ss); int cur_sum = 0; rep(i,m) { cur_sum += sum[i]; sum[i] = cur_sum; if(sum[i] <= 1) { cout << "impossible\n"; return 0; } } cur_sum = 0; rep(i,m) { if(sum[i] > 2) cur_sum++; tri_sum[i+1] = cur_sum; } if(siz(big)%2==0) { int color = 0; forall(it,big) { ans[rel_ind[it]] = color; color ^= 1; } forall(it,rest) { ans[rel_ind[it]] = ans[rel_ind[parent[it]]]^1; } rep(i,n) cout << ans[i]; return 0; } if(siz(big) == 1) { ans[rel_ind[big[0]]] = 1; rep(i,n) cout << ans[i]; return 0; } int pot = -1; rep(i,siz(big)) { int l = segs[big[(i+1)%siz(big)]].ff; int r = segs[big[i]].ss; bool is = 0; if(l <= r) { is = (tri_sum[r+1]-tri_sum[l] == r-l+1); } else { is = (tri_sum[m]-tri_sum[l]+tri_sum[r+1] == (r-l+1+m)%m); } if(is) pot = i; } if(pot == -1) cout << "impossible\n"; else { int color = 0; rep(i,siz(big)) { if((i-1+siz(big))%siz(big) == pot) { ans[rel_ind[big[i]]] = color^1; continue; } ans[rel_ind[big[i]]] = color; color ^= 1; } forall(it,rest) { ans[rel_ind[it]] = ans[rel_ind[parent[it]]]^1; } rep(i,n) cout << ans[i]; } }
#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...