#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)
using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;
template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl='\n';
const int mxN=1<<17;
const int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;
int m, n, p[mxN];
vector<ar<int, 3>> v;
vpii v2;
int Find(int u){
return p[u]=(u==p[u]?u:Find(p[u]));
}
void comb(int e1, int e2){
e1=Find(e1); e2=Find(e2);
if(e1!=e2)
p[e2]=e1;
}
struct segment{
int val[2*mxN], mset[2*mxN];
// segment() {memset(mset, -1, sizeof mset);}
void set(int L, int R, int v, int i=1, int lo=0, int hi=mxN){
if(lo>=R||L>=hi) return;
if(L<=lo&&hi<=R){
mset[i]=v;
val[i]=v*(hi-lo);
return;
}
push(i, lo, hi);
int m=(lo+hi)/2;
set(L, R, v, i*2, lo, m);
set(L, R, v, i*2+1, m, hi);
val[i]=val[2*i]+val[2*i+1];
}
int query(int L, int R, int i=1, int lo=0, int hi=mxN){
if(lo>=R||L>=hi) return 0;
if(L<=lo&&hi<=R)
return val[i];
push(i, lo, hi);
int m=(lo+hi)/2;
return query(L, R, i*2, lo, m)+query(L, R, i*2+1, m, hi);
}
void push(int i, int lo, int hi){
int m=(lo+hi)/2;
if(mset[i]!=-1){
set(lo, m, mset[i], i*2, lo, m);
set(m, hi, mset[i], i*2+1, m, hi);
mset[i]=-1;
}
}
} st[2];
set<pii> vals;
vi r;
vector<vi> pts;
void se(int l, int r, int t){
// cout << "SE: " << l << ' ' << r << ' ' << t << nl;
if(r>=m){
st[t].set(0, r+1-m, 1);
st[t].set(l, m, 1);
}
else{
st[t].set(l, r+1, 1);
}
}
int qq(int l, int r, int t){
int res=0;
if(r>=m){
res+=st[t].query(0, r+1-m);
res+=st[t].query(l, m);
}
else{
res+=st[t].query(l, r+1);
}
return res;
}
void proc(int v, int t){
se(v2[v].f, v2[v].s, t);
for(auto q:pts[v]){
se(v2[q].f, v2[q].s, t^1);
}
}
int sz(int l, int r){
if(r>=m){
return r+1-m+(m-l);
}
else{
return r-l+1;
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> m >> n;
memset(st[0].mset, -1, sizeof st[0].mset);
memset(st[1].mset, -1, sizeof st[1].mset);
pts.resize(n);
F0R(i, n) p[i]=i;
F0R(i, n){
int l, r; cin >> l >> r;
l--; r--;
if(r<l) v.pb({l, r+m, i});
else v.pb({l, r, i}), v.pb({l+m, r+m, i});
if(r>=l)
v2.pb({l, r});
else
v2.pb({l, r+m});
se(v2[i].f, v2[i].s, 0);
}
if(st[0].query(0, m)!=m){
cout << "impossible\n";
return 0;
}
st[0].set(0, m, 0);
sort(all(v), [&](ar<int, 3> A, ar<int, 3> B){
if(A[0]==B[0]) return A[1]>B[1];
return A[0]<B[0];
});
for(auto[x, y, i]:v){
// cout << x << ' ' << y << ' ' << i << nl;
// for(auto v:vals) cout << "(" << v.f << ", " << v.s << ")" << ' ';
// cout << nl;
auto it=vals.lower_bound({y, -MOD});
if(i==Find(i)&&it!=vals.end()){
comb(it->s, i);
}
vals.insert({y, i});
}
// we have do deal with odds and evens
F0R(i, n){
if(Find(i)!=i)
pts[Find(i)].pb(i);
else
r.pb(i);
}
sort(all(r), [&](int e1, int e2){
return v2[e1]<v2[e2];
});
int R=siz(r);
// F0R(i, R){
// cout << r[i] << ": ";
// trav(v, pts[r[i]]) cout << v << ' ';
// cout << nl;
// }
// cout << nl;
if(R==1){
// cerr << "HERE\n";
proc(r[0], 0);
if(qq(0, m-1, 0)!=m||qq(0, m-1, 1)!=m){
cout << "impossible\n";
}
else{
F0R(i, n){
if(i==r[0]) cout << 1;
else cout << 0;
}
cout << nl;
}
return 0;
}
F0R(i, R){
int lb=r[(i-1+R)%R], mb=r[i], rb=r[(i+1)%R];
// set lb with 1s
// cout << lb << ' ' << mb << ' ' << rb << nl;
proc(lb, 0); proc(mb, 1); proc(rb, 0);
// cout << qq(v2[mb].f, v2[mb].s, 0) << ' ' << qq(v2[mb].f, v2[mb].s, 1) << nl;
// F0R(i, m) cout << st[0].query(i, i+1) << ' ';
// cout << nl;
// F0R(i, m) cout << st[1].query(i, i+1) << ' ';
// cout << nl;
// cout << sz(v2[mb].f, v2[mb].s) << ' ' << qq(v2[mb].f, v2[mb].s, 0) << nl;
if(qq(v2[mb].f, v2[mb].s, 0)!=sz(v2[mb].f, v2[mb].s)){
cout << "impossible\n";
return 0;
}
st[0].set(0, m, 0);
st[1].set(0, m, 0);
}
if(R&1){
F0R(i, R){
int lb=r[(i-1+R)%R], mb1=r[i], mb2=r[(i+1)%R], rb=r[(i+2)%R];
proc(lb, 0); proc(mb1, 1); proc(mb2, 1); proc(rb, 0);
if(v2[mb1].s<v2[mb2].f-1) continue;
if(qq(v2[mb1].f, v2[mb1].s, 0)==sz(v2[mb1].f, v2[mb1].s)&&qq(v2[mb2].f, v2[mb2].s, 0)==sz(v2[mb2].f, v2[mb2].s)){
// we have found a sol
vi ans(n, -1);
int x=0;
F0R(j, n){
ans[r[j]]=i&1^x;
trav(v, pts[r[j]]) ans[v]=i&1^1^x;
if(j==i)
x=1;
}
F0R(i, n) assert(ans[i]!=-1), cout << ans[i];
cout << nl;
return 0;
}
st[0].set(0, m, 0); st[1].set(0, m, 0);
}
cout << "impossible\n";
}
else{
vi ans(n, -1);
F0R(i, R){
ans[r[i]]=i&1;
trav(v, pts[r[i]]) ans[v]=i&1^1;
}
F0R(i, n) assert(ans[i]!=-1), cout << ans[i];
cout << nl;
}
}
Compilation message
alternating.cpp: In function 'int32_t main()':
alternating.cpp:224:32: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
224 | ans[r[j]]=i&1^x;
| ~^~
alternating.cpp:225:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
225 | trav(v, pts[r[j]]) ans[v]=i&1^1^x;
| ~^~
alternating.cpp:241:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
241 | trav(v, pts[r[i]]) ans[v]=i&1^1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2380 KB |
no wires in direction 1 between segments 1 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2380 KB |
no wires in direction 1 between segments 1 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2380 KB |
no wires in direction 1 between segments 1 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
19608 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
99 ms |
12600 KB |
Output is correct |
| 4 |
Correct |
92 ms |
12608 KB |
Output is correct |
| 5 |
Correct |
261 ms |
21260 KB |
Output is correct |
| 6 |
Correct |
172 ms |
20744 KB |
Output is correct |
| 7 |
Runtime error |
233 ms |
38708 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2380 KB |
no wires in direction 1 between segments 1 and 15 |
| 4 |
Halted |
0 ms |
0 KB |
- |
