| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 63667 | zetapi | Alternating Current (BOI18_alternating) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include#include <<bitsbits//stdcstdc++.++.hh>>
usingusing namespacenamespace std std;;
#define#define pb push_back pb push_b
#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);
}
int now=arr[End].start;
if(End<Start)
now+=N;
return now<=high;
}
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;
}