#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
#define start first
#define length second.first
typedef pair<int,int> pii;
const int MAX=1e5;
bool cmp(const pair<int,pii> X,const pair<int,pii> Y)
{
if(X.start==Y.start)
return X.length>Y.length;
return X.start<Y.start;
}
vector<pair<int,pii>> arr;
vector<int> vec,Enclosed[MAX];
int N,M,X,Y,par[MAX],mark[MAX];
int len,cur,pre;
int root(int X)
{
if(par[X]==X)
return X;
return par[X]=root(par[X]);
}
bool Subset(int X,int Y)
{
int RelativeStart=(arr[X].start-arr[Y].start+N)%N;
return RelativeStart+arr[X].length<=arr[Y].length;
}
void Alternate()
{
for(int A=0;A<vec.size();A++)
mark[arr[vec[A]].second.second]=A%2;
for(int A=0;A<vec.size();A++)
{
for(auto B:Enclosed[vec[A]])
mark[arr[B].second.second]=mark[arr[vec[A]].second.second]^1;
}
return ;
}
bool ok()
{
int BIT[MAX];
for(int A=0;A<2;A++)
{
for(int B=0;B<N;B++)
BIT[B]=0;
for(int B=0;B<M;B++)
{
if(mark[arr[B].second.second]!=A)
continue;
//cout<<"original index "<<B<<" start "<<arr[B].start<<" length "<<arr[B].length<<"\n";
if(arr[B].start+arr[B].length-1>=N)
{
BIT[0]++;
BIT[arr[B].start]++;
BIT[(arr[B].start+arr[B].length-1)%N+1]--;
}
else
{
BIT[arr[B].start]++;
BIT[arr[B].start+arr[B].length]--;
}
}
for(int A=0;A<N;A++)
{
BIT[A+1]+=BIT[A];
if(!BIT[A])
return false;
}
}
return true;
}
bool ok(int L,int R,int col)
{
int Start=vec[L];
int End=vec[R];
int len=(End-Start+M-1)%M+1;
int high=arr[Start].start;
for(int A=0;A<len;A++)
{
int cur=(Start+A)%M;
if(mark[arr[cur].second.second]!=col)
continue;
int now=arr[cur].start;
if(cur<Start)
now+=N;
if(now>high)
return false;
high=max(high,now+arr[cur].length);
}
return true;
}
void color(int X,int C)
{
if(C>=0)
mark[arr[vec[X]].second.second]=C;
for(auto A:Enclosed[vec[X]])
mark[arr[A].second.second]=!mark[arr[vec[X]].second.second];
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin>>N>>M;
for(int A=0;A<M;A++)
{
par[A]=A;
cin>>X>>Y;
X--;
Y--;
len=(Y-X+N)%N+1;
arr.pb(mp(X,mp(len,A)));
}
sort(arr.begin(),arr.end(),cmp);
pre=0;
for(int A=1;A<2*M;A++)
{
cur=A%M;
if(Subset(cur,pre))
par[cur]=pre;
else
pre=cur;
}
for(int A=0;A<M;A++)
{
cur=root(A);
if(A==cur)
vec.pb(A);
else
Enclosed[cur].pb(A);
}
if(!(vec.size()%2))
{
Alternate();
if(ok())
for(int A=0;A<M;A++)
cout<<mark[A];
else
cout<<"impossible\n";
return 0;
}
else
{
for(int A=0;A<vec.size();A++)
{
int a=(A+0+vec.size())%vec.size();
int b=(A+1+vec.size())%vec.size();
int c=(A+2+vec.size())%vec.size();
int d=(A+3+vec.size())%vec.size();
color(a,1);
color(b,0);
color(c,0);
color(d,1);
if(ok(a,d,1))
{
for(int A=0;A<vec.size();A++)
{
int cur=(d+A)%vec.size();
if(cur==a or cur==b or cur==c or cur==d)
continue;
mark[arr[vec[cur]].second.second]=!mark[arr[vec[(cur-1+vec.size())%vec.size()]].second.second];
}
for(int A=0;A<vec.size();A++)
color(A,-1);
if(ok())
{
for(int A=0;A<M;A++)
cout<<mark[A];
return 0;
}
else
cout<<"impossible";
return 0;
}
}
}
cout<<"impossible";
return 0;
}
Compilation message
alternating.cpp: In function 'void Alternate()':
alternating.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size();A++)
~^~~~~~~~~~~
alternating.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size();A++)
~^~~~~~~~~~~
alternating.cpp: In function 'int main()':
alternating.cpp:162:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size();A++)
~^~~~~~~~~~~
alternating.cpp:174:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size();A++)
~^~~~~~~~~~~
alternating.cpp:181:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<vec.size();A++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2788 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2840 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2788 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2840 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2788 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2840 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
9440 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9440 KB |
Output is correct |
| 3 |
Correct |
37 ms |
9440 KB |
Output is correct |
| 4 |
Correct |
37 ms |
9440 KB |
Output is correct |
| 5 |
Correct |
97 ms |
9440 KB |
Output is correct |
| 6 |
Correct |
104 ms |
9440 KB |
Output is correct |
| 7 |
Correct |
71 ms |
9440 KB |
Output is correct |
| 8 |
Correct |
7 ms |
9440 KB |
Output is correct |
| 9 |
Correct |
6 ms |
9440 KB |
Output is correct |
| 10 |
Correct |
107 ms |
9440 KB |
Output is correct |
| 11 |
Correct |
54 ms |
9440 KB |
Output is correct |
| 12 |
Correct |
65 ms |
9440 KB |
Output is correct |
| 13 |
Correct |
5 ms |
9440 KB |
Output is correct |
| 14 |
Correct |
5 ms |
9440 KB |
Output is correct |
| 15 |
Correct |
72 ms |
9668 KB |
Output is correct |
| 16 |
Correct |
34 ms |
9668 KB |
Output is correct |
| 17 |
Correct |
82 ms |
9668 KB |
Output is correct |
| 18 |
Correct |
74 ms |
9668 KB |
Output is correct |
| 19 |
Correct |
9 ms |
9668 KB |
Output is correct |
| 20 |
Correct |
91 ms |
9668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2788 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2840 KB |
'impossible' claimed, but there is a solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
