oj.uz

Submission #63628

# Submission time Handle Problem Language Result Execution time Memory
63628 2018-08-02T09:23:24 Z zetapi Alternating Current (BOI18_alternating) C++14
19 / 100
 118 ms 22792 KB 
#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)%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(M<=4)
	{
		for(int A=0;A<(1<<M);A++)
		{
			for(int B=0;B<M;B++)
				mark[B]=((A&(1<<B))==0);
			if(ok())
			{
				for(int B=0;B<M;B++)
					cout<<mark[B];
				return 0;
			}
		}
		cout<<"impossible";
		return 0;
	}
	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:178:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int A=0;A<vec.size();A++)
               ~^~~~~~~~~~~
alternating.cpp:190:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int A=0;A<vec.size();A++)
                 ~^~~~~~~~~~~
alternating.cpp:197:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int A=0;A<vec.size();A++)
                 ~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 6 ms 2804 KB Output is correct
5 Correct 7 ms 2872 KB Output is correct
6 Correct 6 ms 2916 KB Output is correct
7 Correct 6 ms 2956 KB Output is correct
8 Correct 6 ms 2956 KB Output is correct
9 Correct 6 ms 2956 KB Output is correct
10 Correct 5 ms 2960 KB Output is correct
11 Correct 7 ms 2960 KB Output is correct
12 Incorrect 8 ms 2960 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 6 ms 2804 KB Output is correct
5 Correct 7 ms 2872 KB Output is correct
6 Correct 6 ms 2916 KB Output is correct
7 Correct 6 ms 2956 KB Output is correct
8 Correct 6 ms 2956 KB Output is correct
9 Correct 6 ms 2956 KB Output is correct
10 Correct 5 ms 2960 KB Output is correct
11 Correct 7 ms 2960 KB Output is correct
12 Incorrect 8 ms 2960 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 6 ms 2804 KB Output is correct
5 Correct 7 ms 2872 KB Output is correct
6 Correct 6 ms 2916 KB Output is correct
7 Correct 6 ms 2956 KB Output is correct
8 Correct 6 ms 2956 KB Output is correct
9 Correct 6 ms 2956 KB Output is correct
10 Correct 5 ms 2960 KB Output is correct
11 Correct 7 ms 2960 KB Output is correct
12 Incorrect 8 ms 2960 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10468 KB Output is correct
2 Correct 9 ms 10468 KB Output is correct
3 Correct 42 ms 10468 KB Output is correct
4 Correct 48 ms 10468 KB Output is correct
5 Correct 102 ms 12296 KB Output is correct
6 Correct 117 ms 13244 KB Output is correct
7 Correct 88 ms 13740 KB Output is correct
8 Correct 10 ms 13740 KB Output is correct
9 Correct 8 ms 13740 KB Output is correct
10 Correct 118 ms 15852 KB Output is correct
11 Correct 79 ms 15852 KB Output is correct
12 Correct 88 ms 17448 KB Output is correct
13 Correct 7 ms 17448 KB Output is correct
14 Correct 8 ms 17448 KB Output is correct
15 Correct 110 ms 19148 KB Output is correct
16 Correct 42 ms 19148 KB Output is correct
17 Correct 91 ms 20392 KB Output is correct
18 Correct 92 ms 21056 KB Output is correct
19 Correct 12 ms 21056 KB Output is correct
20 Correct 110 ms 22792 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 6 ms 2796 KB Output is correct
4 Correct 6 ms 2804 KB Output is correct
5 Correct 7 ms 2872 KB Output is correct
6 Correct 6 ms 2916 KB Output is correct
7 Correct 6 ms 2956 KB Output is correct
8 Correct 6 ms 2956 KB Output is correct
9 Correct 6 ms 2956 KB Output is correct
10 Correct 5 ms 2960 KB Output is correct
11 Correct 7 ms 2960 KB Output is correct
12 Incorrect 8 ms 2960 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -