oj.uz

Submission #63594

# Submission time Handle Problem Language Result Execution time Memory
63594 2018-08-02T08:43:03 Z zetapi Alternating Current (BOI18_alternating) C++14
19 / 100
 113 ms 9640 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);
	}
	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;
}

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:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int A=0;A<vec.size();A++)
               ~^~~~~~~~~~~
alternating.cpp:177:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int A=0;A<vec.size();A++)
                 ~^~~~~~~~~~~
alternating.cpp:184: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 7 ms 2836 KB Output is correct
3 Correct 6 ms 2836 KB Output is correct
4 Correct 5 ms 2836 KB Output is correct
5 Correct 5 ms 2836 KB Output is correct
6 Correct 7 ms 2876 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 5 ms 2876 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Incorrect 4 ms 2944 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 7 ms 2836 KB Output is correct
3 Correct 6 ms 2836 KB Output is correct
4 Correct 5 ms 2836 KB Output is correct
5 Correct 5 ms 2836 KB Output is correct
6 Correct 7 ms 2876 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 5 ms 2876 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Incorrect 4 ms 2944 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 7 ms 2836 KB Output is correct
3 Correct 6 ms 2836 KB Output is correct
4 Correct 5 ms 2836 KB Output is correct
5 Correct 5 ms 2836 KB Output is correct
6 Correct 7 ms 2876 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 5 ms 2876 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Incorrect 4 ms 2944 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 69 ms 9640 KB Output is correct
2 Correct 6 ms 9640 KB Output is correct
3 Correct 38 ms 9640 KB Output is correct
4 Correct 33 ms 9640 KB Output is correct
5 Correct 79 ms 9640 KB Output is correct
6 Correct 85 ms 9640 KB Output is correct
7 Correct 67 ms 9640 KB Output is correct
8 Correct 10 ms 9640 KB Output is correct
9 Correct 7 ms 9640 KB Output is correct
10 Correct 95 ms 9640 KB Output is correct
11 Correct 61 ms 9640 KB Output is correct
12 Correct 64 ms 9640 KB Output is correct
13 Correct 4 ms 9640 KB Output is correct
14 Correct 5 ms 9640 KB Output is correct
15 Correct 102 ms 9640 KB Output is correct
16 Correct 32 ms 9640 KB Output is correct
17 Correct 69 ms 9640 KB Output is correct
18 Correct 75 ms 9640 KB Output is correct
19 Correct 10 ms 9640 KB Output is correct
20 Correct 113 ms 9640 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 7 ms 2836 KB Output is correct
3 Correct 6 ms 2836 KB Output is correct
4 Correct 5 ms 2836 KB Output is correct
5 Correct 5 ms 2836 KB Output is correct
6 Correct 7 ms 2876 KB Output is correct
7 Correct 6 ms 2876 KB Output is correct
8 Correct 5 ms 2876 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Incorrect 4 ms 2944 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -