oj.uz

Submission #63589

# Submission time Handle Problem Language Result Execution time Memory
63589 2018-08-02T08:39:04 Z zetapi Alternating Current (BOI18_alternating) C++14
19 / 100
 101 ms 17512 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(!(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++)
                 ~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2788 KB Output is correct
4 Correct 5 ms 2788 KB Output is correct
5 Correct 5 ms 2788 KB Output is correct
6 Correct 6 ms 2924 KB Output is correct
7 Correct 7 ms 2924 KB Output is correct
8 Correct 6 ms 2924 KB Output is correct
9 Correct 6 ms 2924 KB Output is correct
10 Correct 4 ms 3032 KB Output is correct
11 Correct 4 ms 3032 KB Output is correct
12 Incorrect 4 ms 3032 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 5 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2788 KB Output is correct
4 Correct 5 ms 2788 KB Output is correct
5 Correct 5 ms 2788 KB Output is correct
6 Correct 6 ms 2924 KB Output is correct
7 Correct 7 ms 2924 KB Output is correct
8 Correct 6 ms 2924 KB Output is correct
9 Correct 6 ms 2924 KB Output is correct
10 Correct 4 ms 3032 KB Output is correct
11 Correct 4 ms 3032 KB Output is correct
12 Incorrect 4 ms 3032 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 5 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2788 KB Output is correct
4 Correct 5 ms 2788 KB Output is correct
5 Correct 5 ms 2788 KB Output is correct
6 Correct 6 ms 2924 KB Output is correct
7 Correct 7 ms 2924 KB Output is correct
8 Correct 6 ms 2924 KB Output is correct
9 Correct 6 ms 2924 KB Output is correct
10 Correct 4 ms 3032 KB Output is correct
11 Correct 4 ms 3032 KB Output is correct
12 Incorrect 4 ms 3032 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 61 ms 9508 KB Output is correct
2 Correct 6 ms 9508 KB Output is correct
3 Correct 30 ms 9508 KB Output is correct
4 Correct 33 ms 9508 KB Output is correct
5 Correct 101 ms 9508 KB Output is correct
6 Correct 77 ms 9508 KB Output is correct
7 Correct 99 ms 9508 KB Output is correct
8 Correct 9 ms 9508 KB Output is correct
9 Correct 7 ms 9508 KB Output is correct
10 Correct 79 ms 10528 KB Output is correct
11 Correct 72 ms 10528 KB Output is correct
12 Correct 71 ms 12168 KB Output is correct
13 Correct 6 ms 12168 KB Output is correct
14 Correct 6 ms 12168 KB Output is correct
15 Correct 90 ms 13844 KB Output is correct
16 Correct 30 ms 13844 KB Output is correct
17 Correct 97 ms 15080 KB Output is correct
18 Correct 80 ms 15848 KB Output is correct
19 Correct 10 ms 15848 KB Output is correct
20 Correct 94 ms 17512 KB Output is correct

Subtask #5
0 / 26.0

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