Submission #951567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
951567	2024-03-22T06:37:21 Z	mocha	Alternating Current (BOI18_alternating)	C++14	13 / 100	3000 ms	6996 KB

alternating

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;

int n, m;
int ans;

struct Edge {
	int ty;
	int fr, to;
} e[mx];

int main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n >> m;
	for (int i=0;i<m;i++) {
		cin >> e[i].fr >> e[i].to;
		if (e[i].fr == e[i].to) {
			e[i].ty = 0;
		} else if (e[i].fr < e[i].to) {
			e[i].ty = 1;
		} else {
			e[i].ty = 2;
		}
	}
	bool fl = 0;
	for (int i=0;i<(1<<m);i++) {
		set<int> s[2];
		for (int j=0;j<m;j++) {
			int tp = (i&(1<<j)?1:0);
			if (e[j].ty == 0) {
				s[tp].insert(e[j].fr);
			} else if (e[j].ty == 1) {
				for (int k=e[j].fr;k<=e[j].to;k++) {
					s[tp].insert(k);
				}
			} else {
				for (int k=e[j].fr;k<=n;k++) {
					s[tp].insert(k);
				}
				for (int k=1;k<=e[j].to;k++) {
					s[tp].insert(k);
				}
			}
		}
		if (s[0].size() == n and s[1].size() == n) {
			fl = 1;
			ans = i;
			break;
		}
	}
	if (fl) {
		for (int i=0;i<m;i++) {
			cout << ((1<<i)&ans?1:0);
		}
		cout << "\n";
	} else {
		cout << "impossible\n";
	}
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if (s[0].size() == n and s[1].size() == n) {
      |       ~~~~~~~~~~~~^~~~
alternating.cpp:47:40: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if (s[0].size() == n and s[1].size() == n) {
      |                            ~~~~~~~~~~~~^~~~

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	460 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	4 ms	348 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	424 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	52 ms	348 KB	Output is correct
36	Correct	2 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	46 ms	348 KB	Output is correct
39	Correct	1 ms	544 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	460 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	4 ms	348 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	424 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	52 ms	348 KB	Output is correct
36	Correct	2 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	46 ms	348 KB	Output is correct
39	Correct	1 ms	544 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	9 ms	348 KB	Output is correct
43	Incorrect	1 ms	344 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	1 ms	456 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	460 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	4 ms	348 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	424 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	52 ms	348 KB	Output is correct
36	Correct	2 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	46 ms	348 KB	Output is correct
39	Correct	1 ms	544 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	9 ms	348 KB	Output is correct
43	Incorrect	1 ms	344 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	3015 ms	6996 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	5 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	464 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	460 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	4 ms	348 KB	Output is correct
28	Correct	0 ms	344 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	424 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	52 ms	348 KB	Output is correct
36	Correct	2 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	46 ms	348 KB	Output is correct
39	Correct	1 ms	544 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	9 ms	348 KB	Output is correct
43	Incorrect	1 ms	344 KB	'impossible' claimed, but there is a solution
44	Halted	0 ms	0 KB	-

Submission #951567

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