답안 #63406 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63406	2018-08-01T17:40:33 Z	zetapi	Alternating Current (BOI18_alternating)	C++14	13 / 100	3000 ms	9748 KB

alternating

#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;
}

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);
	}
	/*for(auto A:vec)
	{
		cout<<"Enclosed by "<<A<<"\n";
		for(auto B:Enclosed[A])
			cout<<B<<"\n";
	}*/
	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++)
		{
			Alternate();
			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();
			mark[arr[vec[b]].second.second]=!mark[arr[vec[a]].second.second];
			mark[arr[vec[c]].second.second]=!mark[arr[vec[d]].second.second];
			for(auto B:Enclosed[vec[b]])
				mark[arr[B].second.second]=!mark[arr[vec[b]].second.second];
			for(auto B:Enclosed[vec[c]])
				mark[arr[B].second.second]=!mark[arr[vec[c]].second.second];
			if(ok())
			{
			 	for(int A=0;A<M;A++)
					cout<<mark[A];
				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:138:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int A=0;A<vec.size();A++)
               ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2696 KB	Output is correct
4	Correct	5 ms	2700 KB	Output is correct
5	Correct	5 ms	2872 KB	Output is correct
6	Correct	6 ms	2952 KB	Output is correct
7	Correct	7 ms	2988 KB	Output is correct
8	Correct	5 ms	2988 KB	Output is correct
9	Correct	6 ms	2988 KB	Output is correct
10	Correct	6 ms	2988 KB	Output is correct
11	Correct	5 ms	2988 KB	Output is correct
12	Correct	5 ms	2988 KB	Output is correct
13	Correct	5 ms	2988 KB	Output is correct
14	Correct	7 ms	2988 KB	Output is correct
15	Correct	6 ms	2988 KB	Output is correct
16	Correct	7 ms	3044 KB	Output is correct
17	Correct	8 ms	3044 KB	Output is correct
18	Correct	4 ms	3044 KB	Output is correct
19	Correct	5 ms	3044 KB	Output is correct
20	Correct	6 ms	3044 KB	Output is correct
21	Correct	6 ms	3044 KB	Output is correct
22	Correct	5 ms	3044 KB	Output is correct
23	Correct	5 ms	3044 KB	Output is correct
24	Correct	5 ms	3044 KB	Output is correct
25	Correct	5 ms	3044 KB	Output is correct
26	Correct	4 ms	3044 KB	Output is correct
27	Correct	5 ms	3044 KB	Output is correct
28	Correct	6 ms	3044 KB	Output is correct
29	Correct	4 ms	3044 KB	Output is correct
30	Correct	5 ms	3044 KB	Output is correct
31	Correct	5 ms	3044 KB	Output is correct
32	Correct	6 ms	3044 KB	Output is correct
33	Correct	5 ms	3176 KB	Output is correct
34	Correct	5 ms	3176 KB	Output is correct
35	Correct	5 ms	3176 KB	Output is correct
36	Correct	5 ms	3176 KB	Output is correct
37	Correct	6 ms	3176 KB	Output is correct
38	Correct	6 ms	3176 KB	Output is correct
39	Correct	5 ms	3176 KB	Output is correct
40	Correct	5 ms	3176 KB	Output is correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2696 KB	Output is correct
4	Correct	5 ms	2700 KB	Output is correct
5	Correct	5 ms	2872 KB	Output is correct
6	Correct	6 ms	2952 KB	Output is correct
7	Correct	7 ms	2988 KB	Output is correct
8	Correct	5 ms	2988 KB	Output is correct
9	Correct	6 ms	2988 KB	Output is correct
10	Correct	6 ms	2988 KB	Output is correct
11	Correct	5 ms	2988 KB	Output is correct
12	Correct	5 ms	2988 KB	Output is correct
13	Correct	5 ms	2988 KB	Output is correct
14	Correct	7 ms	2988 KB	Output is correct
15	Correct	6 ms	2988 KB	Output is correct
16	Correct	7 ms	3044 KB	Output is correct
17	Correct	8 ms	3044 KB	Output is correct
18	Correct	4 ms	3044 KB	Output is correct
19	Correct	5 ms	3044 KB	Output is correct
20	Correct	6 ms	3044 KB	Output is correct
21	Correct	6 ms	3044 KB	Output is correct
22	Correct	5 ms	3044 KB	Output is correct
23	Correct	5 ms	3044 KB	Output is correct
24	Correct	5 ms	3044 KB	Output is correct
25	Correct	5 ms	3044 KB	Output is correct
26	Correct	4 ms	3044 KB	Output is correct
27	Correct	5 ms	3044 KB	Output is correct
28	Correct	6 ms	3044 KB	Output is correct
29	Correct	4 ms	3044 KB	Output is correct
30	Correct	5 ms	3044 KB	Output is correct
31	Correct	5 ms	3044 KB	Output is correct
32	Correct	6 ms	3044 KB	Output is correct
33	Correct	5 ms	3176 KB	Output is correct
34	Correct	5 ms	3176 KB	Output is correct
35	Correct	5 ms	3176 KB	Output is correct
36	Correct	5 ms	3176 KB	Output is correct
37	Correct	6 ms	3176 KB	Output is correct
38	Correct	6 ms	3176 KB	Output is correct
39	Correct	5 ms	3176 KB	Output is correct
40	Correct	5 ms	3176 KB	Output is correct
41	Correct	6 ms	3176 KB	Output is correct
42	Incorrect	5 ms	3176 KB	'impossible' claimed, but there is a solution
43	Halted	0 ms	0 KB	-

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2696 KB	Output is correct
4	Correct	5 ms	2700 KB	Output is correct
5	Correct	5 ms	2872 KB	Output is correct
6	Correct	6 ms	2952 KB	Output is correct
7	Correct	7 ms	2988 KB	Output is correct
8	Correct	5 ms	2988 KB	Output is correct
9	Correct	6 ms	2988 KB	Output is correct
10	Correct	6 ms	2988 KB	Output is correct
11	Correct	5 ms	2988 KB	Output is correct
12	Correct	5 ms	2988 KB	Output is correct
13	Correct	5 ms	2988 KB	Output is correct
14	Correct	7 ms	2988 KB	Output is correct
15	Correct	6 ms	2988 KB	Output is correct
16	Correct	7 ms	3044 KB	Output is correct
17	Correct	8 ms	3044 KB	Output is correct
18	Correct	4 ms	3044 KB	Output is correct
19	Correct	5 ms	3044 KB	Output is correct
20	Correct	6 ms	3044 KB	Output is correct
21	Correct	6 ms	3044 KB	Output is correct
22	Correct	5 ms	3044 KB	Output is correct
23	Correct	5 ms	3044 KB	Output is correct
24	Correct	5 ms	3044 KB	Output is correct
25	Correct	5 ms	3044 KB	Output is correct
26	Correct	4 ms	3044 KB	Output is correct
27	Correct	5 ms	3044 KB	Output is correct
28	Correct	6 ms	3044 KB	Output is correct
29	Correct	4 ms	3044 KB	Output is correct
30	Correct	5 ms	3044 KB	Output is correct
31	Correct	5 ms	3044 KB	Output is correct
32	Correct	6 ms	3044 KB	Output is correct
33	Correct	5 ms	3176 KB	Output is correct
34	Correct	5 ms	3176 KB	Output is correct
35	Correct	5 ms	3176 KB	Output is correct
36	Correct	5 ms	3176 KB	Output is correct
37	Correct	6 ms	3176 KB	Output is correct
38	Correct	6 ms	3176 KB	Output is correct
39	Correct	5 ms	3176 KB	Output is correct
40	Correct	5 ms	3176 KB	Output is correct
41	Correct	6 ms	3176 KB	Output is correct
42	Incorrect	5 ms	3176 KB	'impossible' claimed, but there is a solution
43	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	9748 KB	Output is correct
2	Correct	6 ms	9748 KB	Output is correct
3	Correct	33 ms	9748 KB	Output is correct
4	Correct	38 ms	9748 KB	Output is correct
5	Correct	90 ms	9748 KB	Output is correct
6	Execution timed out	3041 ms	9748 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2696 KB	Output is correct
4	Correct	5 ms	2700 KB	Output is correct
5	Correct	5 ms	2872 KB	Output is correct
6	Correct	6 ms	2952 KB	Output is correct
7	Correct	7 ms	2988 KB	Output is correct
8	Correct	5 ms	2988 KB	Output is correct
9	Correct	6 ms	2988 KB	Output is correct
10	Correct	6 ms	2988 KB	Output is correct
11	Correct	5 ms	2988 KB	Output is correct
12	Correct	5 ms	2988 KB	Output is correct
13	Correct	5 ms	2988 KB	Output is correct
14	Correct	7 ms	2988 KB	Output is correct
15	Correct	6 ms	2988 KB	Output is correct
16	Correct	7 ms	3044 KB	Output is correct
17	Correct	8 ms	3044 KB	Output is correct
18	Correct	4 ms	3044 KB	Output is correct
19	Correct	5 ms	3044 KB	Output is correct
20	Correct	6 ms	3044 KB	Output is correct
21	Correct	6 ms	3044 KB	Output is correct
22	Correct	5 ms	3044 KB	Output is correct
23	Correct	5 ms	3044 KB	Output is correct
24	Correct	5 ms	3044 KB	Output is correct
25	Correct	5 ms	3044 KB	Output is correct
26	Correct	4 ms	3044 KB	Output is correct
27	Correct	5 ms	3044 KB	Output is correct
28	Correct	6 ms	3044 KB	Output is correct
29	Correct	4 ms	3044 KB	Output is correct
30	Correct	5 ms	3044 KB	Output is correct
31	Correct	5 ms	3044 KB	Output is correct
32	Correct	6 ms	3044 KB	Output is correct
33	Correct	5 ms	3176 KB	Output is correct
34	Correct	5 ms	3176 KB	Output is correct
35	Correct	5 ms	3176 KB	Output is correct
36	Correct	5 ms	3176 KB	Output is correct
37	Correct	6 ms	3176 KB	Output is correct
38	Correct	6 ms	3176 KB	Output is correct
39	Correct	5 ms	3176 KB	Output is correct
40	Correct	5 ms	3176 KB	Output is correct
41	Correct	6 ms	3176 KB	Output is correct
42	Incorrect	5 ms	3176 KB	'impossible' claimed, but there is a solution
43	Halted	0 ms	0 KB	-

답안 #63406

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 0 / 20.0

Subtask #3 0 / 22.0

Subtask #4 0 / 19.0

Subtask #5 0 / 26.0

Subtask #1
13.0 / 13.0

Subtask #2
0 / 20.0

Subtask #3
0 / 22.0

Subtask #4
0 / 19.0

Subtask #5
0 / 26.0