#include <bits/stdc++.h>
#define L int
#define inf 123456
using namespace std;
int ans[100010],preans[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;
preans[x]=col;
for(i=0;i<v[x].size();i++)
{
if(preans[v[x][i]]==col) E();
if(chk[v[x][i]])
{
chk[v[x][i]]=0;
dfs(v[x][i],3-col);
}
}
}
void coloring(int x,int col){
if(col==1)
{
if(a[x].s<=a[x].e)
{
oneup(1,1,n,a[x].s,a[x].e,1);
}
else
{
oneup(1,1,n,a[x].s,n,1);
oneup(1,1,n,1,a[x].e,1);
}
}
else
{
if(a[x].s<=a[x].e)
{
twoup(1,1,n,a[x].s,a[x].e,1);
}
else
{
twoup(1,1,n,a[x].s,n,1);
twoup(1,1,n,1,a[x].e,1);
}
}
int i;
for(i=0;i<v[x].size();i++)
{
if(!ans[v[x][i]])
{
ans[v[x][i]]=3-col;
coloring(v[x][i],3-col);
}
}
}
L bet(L lnum,L loc){
//printf("%lld %lld %lld\n",a[lnum].s,a[lnum].e,loc);
if(a[lnum].s<=loc) return a[lnum].e>=loc||a[lnum].e<a[lnum].s;
else return loc<=a[lnum].e&&a[lnum].e<a[lnum].s;
}
int main()
{
srand((int)time(NULL));
scanf("%d %d",&n,&m);
L i,j,k;
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,1);
}
}
L st=a[1].s,now=a[1].s,usl=1;
for(i=0;i<n;i++)
{
//printf("%lld %lld\n",now,usl);
ans[usl]=1;
L nex=a[usl].e;
L nnex=nex%n+1;
if(sum(1,1,n,nex)<=2)
{
now=nnex;
usl=lines[now][0];
ans[usl]=1;
if(bet(usl,st)) break;
}
else
{
for(j=nex;;)
{
//printf("%lld\n",j);
L ok=0;
for(k=0;k<lines[j].size();k++)
{
//printf("%lld %lld\n",lines[j][k],nnex);
if(bet(lines[j][k],nnex))
{
//puts("yeah");
ok=1;
now=nnex;
usl=lines[j][k];
ans[usl]=1;
break;
}
}
if(ok) break;
if(j==now) break;
j--;
if(j==0) j=n;
}
if(bet(usl,st)) break;
}
}
for(i=1;i<=m;i++)
{
if(ans[i]==1) printf("1");
else printf("0");
}
}
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 'void coloring(int, int)':
alternating.cpp:172: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:271:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0;k<lines[j].size();k++)
~^~~~~~~~~~~~~~~~
alternating.cpp:191: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:195: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 |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5220 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5244 KB |
no wires in direction 0 between segments 13 and 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5220 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5244 KB |
no wires in direction 0 between segments 13 and 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5220 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5244 KB |
no wires in direction 0 between segments 13 and 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
8012 KB |
Output is correct |
| 2 |
Correct |
87 ms |
8012 KB |
Output is correct |
| 3 |
Correct |
93 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
133 ms |
10460 KB |
Output is correct |
| 5 |
Incorrect |
374 ms |
16008 KB |
no wires in direction 0 between segments 17946 and 17949 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5220 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5244 KB |
no wires in direction 0 between segments 13 and 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
