Submission #63055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63055	2018-07-31T13:03:15 Z	zetapi	Alternating Current (BOI18_alternating)	C++14	13 / 100	3000 ms	4088 KB

alternating

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;

int N,M,X[MAX],Y[MAX],mark[MAX][2];

bool ok(int mask)
{
	for(int A=0;A<N;A++)
	{
		mark[A][0]=0;
		mark[A][1]=0;
	}
	for(int A=0;A<M;A++)
	{
		if(X[A]>Y[A])
		{
			for(int B=X[A];B<N;B++)
				mark[B][((mask&(1<<A))!=0)]=1;
			for(int B=0;B<=Y[A];B++)
				mark[B][((mask&(1<<A))!=0)]=1;
		}
		else
		{
			for(int B=X[A];B<=Y[A];B++)
				mark[B][((mask&(1<<A))!=0)]=1;
		}
	}
	for(int A=0;A<N;A++)
		if(mark[A][0]+mark[A][1]!=2)
			return false;
	return true;
}

signed main()
{
	ios_base::sync_with_stdio(false);

	cin>>N>>M;
	for(int A=0;A<M;A++)
	{
		cin>>X[A]>>Y[A];
		X[A]--;
		Y[A]--;
	}
	for(int A=0;A<(1<<M);A++)
	{
		if(ok(A))
		{
			for(int C=0;C<M;C++)
				cout<<(((A&(1<<C))!=0)?1:0);
			return 0;
		}
	}
	cout<<"impossible";
	return 0;
}

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	528 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	4 ms	612 KB	Output is correct
6	Correct	3 ms	656 KB	Output is correct
7	Correct	3 ms	656 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct
12	Correct	3 ms	700 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	3 ms	716 KB	Output is correct
16	Correct	5 ms	720 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	728 KB	Output is correct
19	Correct	4 ms	732 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	740 KB	Output is correct
22	Correct	4 ms	740 KB	Output is correct
23	Correct	3 ms	740 KB	Output is correct
24	Correct	3 ms	740 KB	Output is correct
25	Correct	3 ms	740 KB	Output is correct
26	Correct	3 ms	760 KB	Output is correct
27	Correct	4 ms	760 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	772 KB	Output is correct
30	Correct	2 ms	776 KB	Output is correct
31	Correct	3 ms	780 KB	Output is correct
32	Correct	2 ms	884 KB	Output is correct
33	Correct	3 ms	884 KB	Output is correct
34	Correct	4 ms	920 KB	Output is correct
35	Correct	8 ms	920 KB	Output is correct
36	Correct	3 ms	920 KB	Output is correct
37	Correct	3 ms	920 KB	Output is correct
38	Correct	6 ms	920 KB	Output is correct
39	Correct	2 ms	920 KB	Output is correct
40	Correct	3 ms	920 KB	Output is correct

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	528 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	4 ms	612 KB	Output is correct
6	Correct	3 ms	656 KB	Output is correct
7	Correct	3 ms	656 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct
12	Correct	3 ms	700 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	3 ms	716 KB	Output is correct
16	Correct	5 ms	720 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	728 KB	Output is correct
19	Correct	4 ms	732 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	740 KB	Output is correct
22	Correct	4 ms	740 KB	Output is correct
23	Correct	3 ms	740 KB	Output is correct
24	Correct	3 ms	740 KB	Output is correct
25	Correct	3 ms	740 KB	Output is correct
26	Correct	3 ms	760 KB	Output is correct
27	Correct	4 ms	760 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	772 KB	Output is correct
30	Correct	2 ms	776 KB	Output is correct
31	Correct	3 ms	780 KB	Output is correct
32	Correct	2 ms	884 KB	Output is correct
33	Correct	3 ms	884 KB	Output is correct
34	Correct	4 ms	920 KB	Output is correct
35	Correct	8 ms	920 KB	Output is correct
36	Correct	3 ms	920 KB	Output is correct
37	Correct	3 ms	920 KB	Output is correct
38	Correct	6 ms	920 KB	Output is correct
39	Correct	2 ms	920 KB	Output is correct
40	Correct	3 ms	920 KB	Output is correct
41	Correct	2 ms	920 KB	Output is correct
42	Correct	3 ms	920 KB	Output is correct
43	Incorrect	2 ms	920 KB	'impossible' claimed, but there is a solution
44	Halted	0 ms	0 KB	-

Subtask #3
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	528 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	4 ms	612 KB	Output is correct
6	Correct	3 ms	656 KB	Output is correct
7	Correct	3 ms	656 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct
12	Correct	3 ms	700 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	3 ms	716 KB	Output is correct
16	Correct	5 ms	720 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	728 KB	Output is correct
19	Correct	4 ms	732 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	740 KB	Output is correct
22	Correct	4 ms	740 KB	Output is correct
23	Correct	3 ms	740 KB	Output is correct
24	Correct	3 ms	740 KB	Output is correct
25	Correct	3 ms	740 KB	Output is correct
26	Correct	3 ms	760 KB	Output is correct
27	Correct	4 ms	760 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	772 KB	Output is correct
30	Correct	2 ms	776 KB	Output is correct
31	Correct	3 ms	780 KB	Output is correct
32	Correct	2 ms	884 KB	Output is correct
33	Correct	3 ms	884 KB	Output is correct
34	Correct	4 ms	920 KB	Output is correct
35	Correct	8 ms	920 KB	Output is correct
36	Correct	3 ms	920 KB	Output is correct
37	Correct	3 ms	920 KB	Output is correct
38	Correct	6 ms	920 KB	Output is correct
39	Correct	2 ms	920 KB	Output is correct
40	Correct	3 ms	920 KB	Output is correct
41	Correct	2 ms	920 KB	Output is correct
42	Correct	3 ms	920 KB	Output is correct
43	Incorrect	2 ms	920 KB	'impossible' claimed, but there is a solution
44	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3057 ms	4088 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	528 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	4 ms	612 KB	Output is correct
6	Correct	3 ms	656 KB	Output is correct
7	Correct	3 ms	656 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct
12	Correct	3 ms	700 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	3 ms	712 KB	Output is correct
15	Correct	3 ms	716 KB	Output is correct
16	Correct	5 ms	720 KB	Output is correct
17	Correct	3 ms	724 KB	Output is correct
18	Correct	3 ms	728 KB	Output is correct
19	Correct	4 ms	732 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	740 KB	Output is correct
22	Correct	4 ms	740 KB	Output is correct
23	Correct	3 ms	740 KB	Output is correct
24	Correct	3 ms	740 KB	Output is correct
25	Correct	3 ms	740 KB	Output is correct
26	Correct	3 ms	760 KB	Output is correct
27	Correct	4 ms	760 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	772 KB	Output is correct
30	Correct	2 ms	776 KB	Output is correct
31	Correct	3 ms	780 KB	Output is correct
32	Correct	2 ms	884 KB	Output is correct
33	Correct	3 ms	884 KB	Output is correct
34	Correct	4 ms	920 KB	Output is correct
35	Correct	8 ms	920 KB	Output is correct
36	Correct	3 ms	920 KB	Output is correct
37	Correct	3 ms	920 KB	Output is correct
38	Correct	6 ms	920 KB	Output is correct
39	Correct	2 ms	920 KB	Output is correct
40	Correct	3 ms	920 KB	Output is correct
41	Correct	2 ms	920 KB	Output is correct
42	Correct	3 ms	920 KB	Output is correct
43	Incorrect	2 ms	920 KB	'impossible' claimed, but there is a solution
44	Halted	0 ms	0 KB	-

Submission #63055

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