#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef double db;
typedef long long LL;
int get(){
char ch;
while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
if (ch=='-'){
int s=0;
while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
return -s;
}
int s=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
return s;
}
const int N = 2e5+5;
int n,m;
struct section{
int l,r,id;
section(const int l_=0,const int r_=0){l=l_;r=r_;}
}s[N],a[N],b[N];
int ka,kb;
bool cmp(section a,section b){return a.l!=b.l?a.l<b.l:a.r>b.r;}
int ans[N];
int Rig[N];
int to[N];
int lst[N],nxt[N];
int getlst(int x){return lst[x]==x?x:lst[x]=getlst(lst[x]);}
int getnxt(int x){return nxt[x]==x?x:nxt[x]=getnxt(nxt[x]);}
int be[N];
int cnt;
void update(int x){
int l=getlst(x),r=getnxt(x);
bool cg=0;
int ll=(l+ka-2)%ka+1,rr=r%ka+1;
if (cnt<ka-1&&getnxt(to[r])==getnxt(rr)){
nxt[r]=rr;
lst[rr]=r;
cnt++;
cg=1;
}
if (cnt<ka-1&&getlst(to[ll])==getlst(x)){
lst[l]=ll;
nxt[ll]=l;
cnt++;
cg=1;
}
if (cg)update(x);
}
int p1[N],p2[N];
int k1,k2;
int ad[N];
bool can(int k,section *a){
fo(i,1,n+1)ad[i]=0;
fo(i,1,k){
if (a[i].r<=n){
ad[a[i].l]++;
ad[a[i].r+1]--;
}
else{
ad[a[i].l]++;
ad[n+1]--;
ad[1]++;
ad[a[i].r-n+1]--;
}
}
fo(i,1,n)ad[i]+=ad[i-1];
bool yes=1;
fo(i,1,n)yes&=(ad[i]>0);
return yes;
}
int main(){
n=get();m=get();
int pm=m;
fo(i,1,m){
s[i].l=get();s[i].r=get();
if (s[i].r<s[i].l)s[i].r+=n;
s[i].id=i;
}
sort(s+1,s+1+m,cmp);
int mx=0;
int m_=0;
fo(i,1,m)
if (s[i].r<=mx)s[++m_]=s[i];
else{
mx=s[i].r;
a[++ka]=s[i];
}
int w=1;
for(;w<=ka&&a[w].r<=mx-n;w++)s[++m_]=a[w];
w--;
m=m_;
fo(i,1,ka-w)a[i]=a[i+w];
ka-=w;
sort(s+1,s+1+m,cmp);
mx=m_=0;
fo(i,1,m)
if(s[i].r<=mx)s[++m_]=s[i];
else{
mx=s[i].r;
b[++kb]=s[i];
}
if (!can(ka,a))return printf("impossible\n"),0;
if(can(kb,b)){
fo(i,1,pm)ans[i]=0;
fo(i,1,ka)ans[a[i].id]=1;
fo(i,1,pm)putchar('0'+ans[i]);
putchar('\n');
return 0;
}
fo(i,1,kb)b[kb+i]=section(b[i].l+n,b[i].r+n);
fd(i,kb*2,1){
if (i==kb*2||b[i].r<b[i+1].l-1)Rig[i]=b[i].r;
else Rig[i]=Rig[i+1];
}
fo(i,1,ka){
int l=1,r=kb*2,w=-1;
for(;l<=r;){
int mid=(l+r)/2;
if (b[mid].l-1<=a[i].r)w=mid,l=mid+1;
else r=mid-1;
}
int p=a[i].r;
if(w!=-1)p=max(p,Rig[w]);
if (p>=n){
to[i]=ka;
l=1,r=ka,w=-1;
for(;l<=r;){
int mid=(l+r)/2;
if (a[mid].l-1<=p-n)w=mid,l=mid+1;
else r=mid-1;
}
if(w!=-1){
w=min(w,i);
to[i]=w;
}
}
else{
l=1,r=ka,w=-1;
for(;l<=r;){
int mid=(l+r)/2;
if (a[mid].l-1<=p)w=mid,l=mid+1;
else r=mid-1;
}
to[i]=w;
}
}
fo(i,1,ka)lst[i]=nxt[i]=i;
fo(i,1,ka)
update(i);
if (cnt==ka-1)return printf("impossible\n"),0;
if ((ka-cnt)&1){
bool yes=0;
fo(i,1,ka){
int x=getnxt(i);
int y=getnxt(x%ka+1);
y=getnxt(y%ka+1);
if (getnxt(to[x])!=y){
x=getnxt(x%ka+1);
nxt[x]=x%ka+1;
lst[x%ka+1]=x;
yes=1;
break;
}
}
if (!yes)return printf("impossible\n"),0;
}
int x=getlst(1),now=1;
for(;!be[x];){
int y=getnxt(x)%ka+1;
for(int p=x;p!=y;p=p%ka+1)be[p]=now;
now=3-now;
}
fo(i,1,ka)if (be[i]==1)p1[++k1]=i;
fo(i,1,k1){
ans[a[p1[i]].id]=1;
int x=p1[i],y=p1[i%k1+1];
int now,pos;
if (y>x&&a[x].r>=a[y].l-1)continue;
if (x>y&&a[x].r-n>=a[y].l-1)continue;
now=a[x].r;
if (i<k1)pos=a[y].l-1;else pos=a[y].l+n-1;
for(;now<pos;){
int l=1,r=kb*2,w=-1;
for(;l<=r;){
int mid=(l+r)/2;
if (b[mid].l-1<=now)w=mid,l=mid+1;
else r=mid-1;
}
now=b[w].r;
ans[b[w].id]=1;
}
}
fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
return 0;
}
Compilation message
alternating.cpp: In function 'int main()':
alternating.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define fo(i,a,b) for(int i=a;i<=b;i++)
^
alternating.cpp:212:2: note: in expansion of macro 'fo'
fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
^~
alternating.cpp:212:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
fo(i,1,pm)putchar('0'+ans[i]);putchar('\n');
^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 3 |
Execution timed out |
3031 ms |
7424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 3 |
Execution timed out |
3031 ms |
7424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 3 |
Execution timed out |
3031 ms |
7424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
9232 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 3 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
19 ms |
8616 KB |
Output is correct |
| 5 |
Execution timed out |
3101 ms |
9848 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7424 KB |
Output is correct |
| 3 |
Execution timed out |
3031 ms |
7424 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
