oj.uz

답안 #63590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63590 2018-08-02T08:39:31 Z zetapi Alternating Current (BOI18_alternating) C++14
19 / 100
 107 ms 9668 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-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++)
                 ~^~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 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 -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 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

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 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 -