#include <bits/stdc++.h>
#define L int
#define inf 123456
using namespace std;
int ans[100010];
int n,m;
vector<int>v[100010],lines[100010];
int chk[100010];
struct S{
int s,e,ord;
}a[100010];
int tr[400040],one[400040],two[400040];
int onetr[400040],twotr[400040];
void update(int now,int S,int E,int s,int e,int val,int num){
if(S>e||E<s) return;
if(s<=S&&E<=e)
{
tr[now]+=val;
return;
}
int mid=(S+E)/2;
update(now*2,S,mid,s,e,val,num);
update(now*2+1,mid+1,E,s,e,val,num);
}
void initone(int now,int S,int E){
one[now]=inf;
if(S==E) return;
int mid=(S+E)/2;
initone(now*2,S,mid);
initone(now*2+1,mid+1,E);
}
void updateone(int now,int S,int E,int s,int e,int val,int num){
if(S>e||E<s) return;
//printf("%d %d %d %d %d %d %d\n",now,S,E,s,e,val,num);
if(s<=S&&E<=e)
{
one[now]=min(one[now],num);
return;
}
int mid=(S+E)/2;
updateone(now*2,S,mid,s,e,val,num);
updateone(now*2+1,mid+1,E,s,e,val,num);
}
void updatetwo(int now,int S,int E,int s,int e,int val,int num){
if(S>e||E<s) return;
if(s<=S&&E<=e)
{
two[now]=max(two[now],num);
return;
}
int mid=(S+E)/2;
updatetwo(now*2,S,mid,s,e,val,num);
updatetwo(now*2+1,mid+1,E,s,e,val,num);
}
int sum(int now,int S,int E,int loc){
if(S>loc||E<loc) return 0;
if(S==E) return tr[now];
int mid=(S+E)/2;
return tr[now]+sum(now*2,S,mid,loc)+sum(now*2+1,mid+1,E,loc);
}
int getone(int now,int S,int E,int loc){
//printf("%d %d %d %d\n",now,S,E,loc);
if(S>loc||E<loc) return inf;
if(S==E) return one[now];
int mid=(S+E)/2;
return min(one[now],min(getone(now*2,S,mid,loc),getone(now*2+1,mid+1,E,loc)));
}
int gettwo(int now,int S,int E,int loc){
//printf("%d %d %d %d\n",now,S,E,loc);
if(S>loc||E<loc) return 0;
if(S==E) return two[now];
int mid=(S+E)/2;
return max(two[now],max(gettwo(now*2,S,mid,loc),gettwo(now*2+1,mid+1,E,loc)));
}
void oneup(int now,int S,int E,int s,int e,int val){
if(S>e||E<s) return;
if(s<=S&&E<=e)
{
onetr[now]+=val;
return;
}
int mid=(S+E)/2;
oneup(now*2,S,mid,s,e,val);
oneup(now*2+1,mid+1,E,s,e,val);
}
void twoup(int now,int S,int E,int s,int e,int val){
if(S>e||E<s) return;
if(s<=S&&E<=e)
{
twotr[now]+=val;
return;
}
int mid=(S+E)/2;
twoup(now*2,S,mid,s,e,val);
twoup(now*2+1,mid+1,E,s,e,val);
}
int oneget(int now,int S,int E,int loc){
if(S>loc||E<loc) return 0;
if(onetr[now]) return 1;
if(S==E) return 0;
L mid=(S+E)/2;
return oneget(now*2,S,mid,loc)||oneget(now*2+1,mid+1,E,loc);
}
int twoget(int now,int S,int E,int loc){
if(S>loc||E<loc) return 0;
if(twotr[now]) return 1;
if(S==E) return 0;
L mid=(S+E)/2;
return twoget(now*2,S,mid,loc)||twoget(now*2+1,mid+1,E,loc);
}
void E(){
puts("impossible");
exit(0);
}
void dfs(int x,int col){
int i;
ans[x]=col;
for(i=0;i<v[x].size();i++)
{
if(ans[v[x][i]]==col) E();
if(chk[v[x][i]])
{
chk[v[x][i]]=0;
dfs(v[x][i],3-col);
}
}
}
int main()
{
srand((int)time(NULL));
scanf("%d %d",&n,&m);
L i,j;
for(i=1;i<=m;i++)
{
scanf("%d %d",&a[i].s,&a[i].e);
lines[a[i].s].push_back(i);
a[i].ord=i;
if(a[i].s<=a[i].e) update(1,1,n,a[i].s,a[i].e,1,i);
else
{
update(1,1,n,1,a[i].e,1,i);
update(1,1,n,a[i].s,n,1,i);
}
}
initone(1,1,n);
for(i=1;i<=m;i++)
{
if(a[i].s<=a[i].e) updateone(1,1,n,a[i].s,a[i].e,1,i);
else
{
updateone(1,1,n,1,a[i].e,1,i);
updateone(1,1,n,a[i].s,n,1,i);
}
}
for(i=1;i<=m;i++)
{
if(a[i].s<=a[i].e) updatetwo(1,1,n,a[i].s,a[i].e,1,i);
else
{
updatetwo(1,1,n,1,a[i].e,1,i);
updatetwo(1,1,n,a[i].s,n,1,i);
}
}
/*for(i=1;i<=4*n;i++)
{
printf("%lld %lld\n",i,one[i]);
}*/
for(i=1;i<=n;i++)
{
L temp=sum(1,1,n,i);
if(temp<=1) E();
else if(temp<=2)
{
L temp1=getone(1,1,n,i),temp2=gettwo(1,1,n,i);
//printf("%d %d %d\n",i,temp1,temp2);
v[temp1].push_back(temp2);
v[temp2].push_back(temp1);
chk[temp1]=chk[temp2]=1;
}
}
for(i=1;i<=m;i++)
{
if(chk[i])
{
chk[i]=0;
dfs(i,rand()%2+1);
}
}
for(i=1;i<=m;i++)
{
if(ans[i]==1)
{
if(a[i].s<=a[i].e)
{
oneup(1,1,n,a[i].s,a[i].e,1);
}
else
{
oneup(1,1,n,1,a[i].s,1);
oneup(1,1,n,a[i].e,n,1);
}
}
else
{
if(a[i].s<=a[i].e)
{
twoup(1,1,n,a[i].s,a[i].e,1);
}
else
{
twoup(1,1,n,1,a[i].s,1);
twoup(1,1,n,a[i].e,n,1);
}
}
//printf("%d ",ans[i]);
}
for(i=1;i<=n;i++)
{
L temp1=oneget(1,1,n,i);
L temp2=twoget(1,1,n,i);
if(!temp1)
{
for(j=0;j<lines[i].size();i++)
{
if(!ans[lines[i][j]])
{
ans[lines[i][j]]=1;
if(a[lines[i][j]].s<=a[lines[i][j]].e)
{
oneup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
}
else
{
oneup(1,1,n,a[lines[i][j]].s,n,1);
oneup(1,1,n,1,a[lines[i][j]].e,1);
}
break;
}
}
}
if(!temp2)
{
for(j=0;j<lines[i].size();i++)
{
if(!ans[lines[i][j]])
{
ans[lines[i][j]]=2;
if(a[lines[i][j]].s<=a[lines[i][j]].e)
{
twoup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
}
else
{
twoup(1,1,n,a[lines[i][j]].s,n,1);
twoup(1,1,n,1,a[lines[i][j]].e,1);
}
break;
}
}
}
}
for(i=1;i<=m;i++)
{
if(ans[i]==1) printf("0");
else if(ans[i]==2) printf("1");
else if(rand()%2) printf("0");
else printf("1");
}
}
Compilation message
alternating.cpp: In function 'void dfs(int, int)':
alternating.cpp:134:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
alternating.cpp: In function 'int main()':
alternating.cpp:241:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<lines[i].size();i++)
~^~~~~~~~~~~~~~~~
alternating.cpp:261:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<lines[i].size();i++)
~^~~~~~~~~~~~~~~~
alternating.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
alternating.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i].s,&a[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5188 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5232 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5356 KB |
no wires in direction 0 between segments 7 and 8 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5188 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5232 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5356 KB |
no wires in direction 0 between segments 7 and 8 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5188 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5232 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5356 KB |
no wires in direction 0 between segments 7 and 8 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
8112 KB |
Output is correct |
| 2 |
Correct |
79 ms |
8112 KB |
Output is correct |
| 3 |
Correct |
80 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
137 ms |
11596 KB |
Output is correct |
| 5 |
Correct |
401 ms |
17612 KB |
Output is correct |
| 6 |
Correct |
206 ms |
17612 KB |
Output is correct |
| 7 |
Incorrect |
372 ms |
17988 KB |
no wires in direction 0 between segments 10406 and 10406 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5188 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5232 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 6 |
Incorrect |
8 ms |
5356 KB |
no wires in direction 0 between segments 7 and 8 |
| 7 |
Halted |
0 ms |
0 KB |
- |
