답안 #41502 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41502	2018-02-17T14:34:58 Z	aome	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2000 ms	36028 KB

sequence

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

const int N = 400005;

vector<int> vec, res;
vector<int> G[N];
int vis[N];
int n, m;
bool ok;

void dfs(int u, bool trace) {
	vis[u] = 1;
	for (auto v : G[u]) {
		if (!vis[v]) dfs(v, trace);
		else ok &= vis[v] == 2;
	}
	vis[u] = 2;
	if (trace) vec.push_back(u); 
}

bool check(int x, bool trace) {
	for (int i = 0; i <= x; ++i) {
		G[i].clear(), vis[i] = 0;
	}
	// u -> v <-> S(u) < S(v)
	for (int i = n; i <= x; ++i) {
		G[i].push_back(i - n);
	}
	for (int i = m; i <= x; ++i) {
		G[i - m].push_back(i);
	}
	ok = 1;
	for (int i = 0; i <= x; ++i) {
		if (!vis[i]) dfs(i, trace);
	}
	return ok;
}

void solve() {
	cin >> n >> m;
	int l = 0, r = max(n, m) * 2;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (check(mid, 0)) l = mid;
		else r = mid - 1;
	}
	vec.clear(), check(l, 1);
	reverse(vec.begin(), vec.end());
	int len = vec.size(), pos0 = 0;
	for (int i = 0; i < len; ++i) if (!vec[i]) pos0 = i;
	res.assign(len, 0);
	for (int i = 0; i < len; ++i) {
		res[vec[i]] = i - pos0;
	}
	cout << len - 1 << '\n';
	for (int i = 1; i < len; ++i) cout << res[i] - res[i - 1] << ' '; cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t; while (t--) solve();
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Ok
2	Correct	9 ms	9828 KB	Ok
3	Correct	11 ms	9936 KB	Ok
4	Correct	10 ms	9936 KB	Ok
5	Correct	11 ms	10048 KB	Ok
6	Correct	12 ms	10048 KB	Ok
7	Correct	12 ms	10048 KB	Ok
8	Correct	10 ms	10048 KB	Ok
9	Correct	12 ms	10076 KB	Ok
10	Correct	12 ms	10080 KB	Ok
11	Correct	9 ms	10084 KB	Ok
12	Correct	10 ms	10088 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	10092 KB	Ok
2	Correct	10 ms	10156 KB	Ok
3	Correct	9 ms	10156 KB	Ok
4	Correct	9 ms	10156 KB	Ok
5	Correct	10 ms	10156 KB	Ok
6	Correct	15 ms	10416 KB	Ok
7	Correct	46 ms	11816 KB	Ok
8	Correct	26 ms	11816 KB	Ok
9	Correct	51 ms	12224 KB	Ok
10	Correct	31 ms	12224 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	12224 KB	Ok
2	Correct	9 ms	12224 KB	Ok
3	Correct	10 ms	12224 KB	Ok
4	Correct	9 ms	12224 KB	Ok
5	Correct	11 ms	12224 KB	Ok
6	Correct	9 ms	12224 KB	Ok
7	Correct	9 ms	12224 KB	Ok
8	Correct	10 ms	12224 KB	Ok
9	Correct	11 ms	12224 KB	Ok
10	Correct	9 ms	12224 KB	Ok
11	Correct	9 ms	12224 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	12224 KB	Ok
2	Correct	11 ms	12224 KB	Ok
3	Correct	10 ms	12224 KB	Ok
4	Correct	10 ms	12224 KB	Ok
5	Correct	10 ms	12224 KB	Ok
6	Correct	415 ms	30400 KB	Ok
7	Correct	324 ms	33280 KB	Ok
8	Correct	628 ms	35080 KB	Ok
9	Correct	492 ms	35080 KB	Ok
10	Correct	327 ms	35080 KB	Ok
11	Correct	597 ms	36028 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Ok
2	Correct	9 ms	9828 KB	Ok
3	Correct	11 ms	9936 KB	Ok
4	Correct	10 ms	9936 KB	Ok
5	Correct	11 ms	10048 KB	Ok
6	Correct	12 ms	10048 KB	Ok
7	Correct	12 ms	10048 KB	Ok
8	Correct	10 ms	10048 KB	Ok
9	Correct	12 ms	10076 KB	Ok
10	Correct	12 ms	10080 KB	Ok
11	Correct	9 ms	10084 KB	Ok
12	Correct	10 ms	10088 KB	Ok
13	Correct	9 ms	12224 KB	Ok
14	Correct	9 ms	12224 KB	Ok
15	Correct	10 ms	12224 KB	Ok
16	Correct	9 ms	12224 KB	Ok
17	Correct	11 ms	12224 KB	Ok
18	Correct	9 ms	12224 KB	Ok
19	Correct	9 ms	12224 KB	Ok
20	Correct	10 ms	12224 KB	Ok
21	Correct	11 ms	12224 KB	Ok
22	Correct	9 ms	12224 KB	Ok
23	Correct	9 ms	12224 KB	Ok
24	Correct	14 ms	36028 KB	Ok
25	Correct	15 ms	36028 KB	Ok
26	Correct	16 ms	36028 KB	Ok
27	Correct	13 ms	36028 KB	Ok
28	Correct	14 ms	36028 KB	Ok
29	Correct	12 ms	36028 KB	Ok
30	Correct	13 ms	36028 KB	Ok
31	Correct	15 ms	36028 KB	Ok
32	Correct	13 ms	36028 KB	Ok
33	Correct	13 ms	36028 KB	Ok
34	Correct	23 ms	36028 KB	Ok
35	Correct	24 ms	36028 KB	Ok
36	Correct	25 ms	36028 KB	Ok
37	Correct	23 ms	36028 KB	Ok
38	Correct	22 ms	36028 KB	Ok
39	Correct	23 ms	36028 KB	Ok
40	Correct	24 ms	36028 KB	Ok
41	Correct	24 ms	36028 KB	Ok
42	Correct	23 ms	36028 KB	Ok
43	Correct	29 ms	36028 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Ok
2	Correct	9 ms	9828 KB	Ok
3	Correct	11 ms	9936 KB	Ok
4	Correct	10 ms	9936 KB	Ok
5	Correct	11 ms	10048 KB	Ok
6	Correct	12 ms	10048 KB	Ok
7	Correct	12 ms	10048 KB	Ok
8	Correct	10 ms	10048 KB	Ok
9	Correct	12 ms	10076 KB	Ok
10	Correct	12 ms	10080 KB	Ok
11	Correct	9 ms	10084 KB	Ok
12	Correct	10 ms	10088 KB	Ok
13	Correct	11 ms	10092 KB	Ok
14	Correct	10 ms	10156 KB	Ok
15	Correct	9 ms	10156 KB	Ok
16	Correct	9 ms	10156 KB	Ok
17	Correct	10 ms	10156 KB	Ok
18	Correct	15 ms	10416 KB	Ok
19	Correct	46 ms	11816 KB	Ok
20	Correct	26 ms	11816 KB	Ok
21	Correct	51 ms	12224 KB	Ok
22	Correct	31 ms	12224 KB	Ok
23	Correct	9 ms	12224 KB	Ok
24	Correct	9 ms	12224 KB	Ok
25	Correct	10 ms	12224 KB	Ok
26	Correct	9 ms	12224 KB	Ok
27	Correct	11 ms	12224 KB	Ok
28	Correct	9 ms	12224 KB	Ok
29	Correct	9 ms	12224 KB	Ok
30	Correct	10 ms	12224 KB	Ok
31	Correct	11 ms	12224 KB	Ok
32	Correct	9 ms	12224 KB	Ok
33	Correct	9 ms	12224 KB	Ok
34	Correct	14 ms	36028 KB	Ok
35	Correct	15 ms	36028 KB	Ok
36	Correct	16 ms	36028 KB	Ok
37	Correct	13 ms	36028 KB	Ok
38	Correct	14 ms	36028 KB	Ok
39	Correct	12 ms	36028 KB	Ok
40	Correct	13 ms	36028 KB	Ok
41	Correct	15 ms	36028 KB	Ok
42	Correct	13 ms	36028 KB	Ok
43	Correct	13 ms	36028 KB	Ok
44	Correct	23 ms	36028 KB	Ok
45	Correct	24 ms	36028 KB	Ok
46	Correct	25 ms	36028 KB	Ok
47	Correct	23 ms	36028 KB	Ok
48	Correct	22 ms	36028 KB	Ok
49	Correct	23 ms	36028 KB	Ok
50	Correct	24 ms	36028 KB	Ok
51	Correct	24 ms	36028 KB	Ok
52	Correct	23 ms	36028 KB	Ok
53	Correct	29 ms	36028 KB	Ok
54	Correct	284 ms	36028 KB	Ok
55	Correct	329 ms	36028 KB	Ok
56	Correct	299 ms	36028 KB	Ok
57	Correct	221 ms	36028 KB	Ok
58	Correct	319 ms	36028 KB	Ok
59	Correct	304 ms	36028 KB	Ok
60	Correct	247 ms	36028 KB	Ok
61	Correct	245 ms	36028 KB	Ok
62	Correct	400 ms	36028 KB	Ok
63	Correct	317 ms	36028 KB	Ok
64	Correct	372 ms	36028 KB	Ok
65	Correct	313 ms	36028 KB	Ok
66	Correct	240 ms	36028 KB	Ok
67	Correct	212 ms	36028 KB	Ok
68	Correct	301 ms	36028 KB	Ok
69	Correct	1092 ms	36028 KB	Ok
70	Correct	1318 ms	36028 KB	Ok
71	Correct	1201 ms	36028 KB	Ok
72	Correct	1190 ms	36028 KB	Ok
73	Correct	1390 ms	36028 KB	Ok
74	Correct	1152 ms	36028 KB	Ok
75	Correct	1084 ms	36028 KB	Ok
76	Correct	1317 ms	36028 KB	Ok
77	Correct	1138 ms	36028 KB	Ok
78	Correct	1356 ms	36028 KB	Ok
79	Correct	1093 ms	36028 KB	Ok
80	Correct	1183 ms	36028 KB	Ok
81	Correct	1288 ms	36028 KB	Ok
82	Correct	1351 ms	36028 KB	Ok
83	Correct	1289 ms	36028 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Ok
2	Correct	9 ms	9828 KB	Ok
3	Correct	11 ms	9936 KB	Ok
4	Correct	10 ms	9936 KB	Ok
5	Correct	11 ms	10048 KB	Ok
6	Correct	12 ms	10048 KB	Ok
7	Correct	12 ms	10048 KB	Ok
8	Correct	10 ms	10048 KB	Ok
9	Correct	12 ms	10076 KB	Ok
10	Correct	12 ms	10080 KB	Ok
11	Correct	9 ms	10084 KB	Ok
12	Correct	10 ms	10088 KB	Ok
13	Correct	11 ms	10092 KB	Ok
14	Correct	10 ms	10156 KB	Ok
15	Correct	9 ms	10156 KB	Ok
16	Correct	9 ms	10156 KB	Ok
17	Correct	10 ms	10156 KB	Ok
18	Correct	15 ms	10416 KB	Ok
19	Correct	46 ms	11816 KB	Ok
20	Correct	26 ms	11816 KB	Ok
21	Correct	51 ms	12224 KB	Ok
22	Correct	31 ms	12224 KB	Ok
23	Correct	9 ms	12224 KB	Ok
24	Correct	9 ms	12224 KB	Ok
25	Correct	10 ms	12224 KB	Ok
26	Correct	9 ms	12224 KB	Ok
27	Correct	11 ms	12224 KB	Ok
28	Correct	9 ms	12224 KB	Ok
29	Correct	9 ms	12224 KB	Ok
30	Correct	10 ms	12224 KB	Ok
31	Correct	11 ms	12224 KB	Ok
32	Correct	9 ms	12224 KB	Ok
33	Correct	9 ms	12224 KB	Ok
34	Correct	11 ms	12224 KB	Ok
35	Correct	11 ms	12224 KB	Ok
36	Correct	10 ms	12224 KB	Ok
37	Correct	10 ms	12224 KB	Ok
38	Correct	10 ms	12224 KB	Ok
39	Correct	415 ms	30400 KB	Ok
40	Correct	324 ms	33280 KB	Ok
41	Correct	628 ms	35080 KB	Ok
42	Correct	492 ms	35080 KB	Ok
43	Correct	327 ms	35080 KB	Ok
44	Correct	597 ms	36028 KB	Ok
45	Correct	14 ms	36028 KB	Ok
46	Correct	15 ms	36028 KB	Ok
47	Correct	16 ms	36028 KB	Ok
48	Correct	13 ms	36028 KB	Ok
49	Correct	14 ms	36028 KB	Ok
50	Correct	12 ms	36028 KB	Ok
51	Correct	13 ms	36028 KB	Ok
52	Correct	15 ms	36028 KB	Ok
53	Correct	13 ms	36028 KB	Ok
54	Correct	13 ms	36028 KB	Ok
55	Correct	23 ms	36028 KB	Ok
56	Correct	24 ms	36028 KB	Ok
57	Correct	25 ms	36028 KB	Ok
58	Correct	23 ms	36028 KB	Ok
59	Correct	22 ms	36028 KB	Ok
60	Correct	23 ms	36028 KB	Ok
61	Correct	24 ms	36028 KB	Ok
62	Correct	24 ms	36028 KB	Ok
63	Correct	23 ms	36028 KB	Ok
64	Correct	29 ms	36028 KB	Ok
65	Correct	284 ms	36028 KB	Ok
66	Correct	329 ms	36028 KB	Ok
67	Correct	299 ms	36028 KB	Ok
68	Correct	221 ms	36028 KB	Ok
69	Correct	319 ms	36028 KB	Ok
70	Correct	304 ms	36028 KB	Ok
71	Correct	247 ms	36028 KB	Ok
72	Correct	245 ms	36028 KB	Ok
73	Correct	400 ms	36028 KB	Ok
74	Correct	317 ms	36028 KB	Ok
75	Correct	372 ms	36028 KB	Ok
76	Correct	313 ms	36028 KB	Ok
77	Correct	240 ms	36028 KB	Ok
78	Correct	212 ms	36028 KB	Ok
79	Correct	301 ms	36028 KB	Ok
80	Correct	1092 ms	36028 KB	Ok
81	Correct	1318 ms	36028 KB	Ok
82	Correct	1201 ms	36028 KB	Ok
83	Correct	1190 ms	36028 KB	Ok
84	Correct	1390 ms	36028 KB	Ok
85	Correct	1152 ms	36028 KB	Ok
86	Correct	1084 ms	36028 KB	Ok
87	Correct	1317 ms	36028 KB	Ok
88	Correct	1138 ms	36028 KB	Ok
89	Correct	1356 ms	36028 KB	Ok
90	Correct	1093 ms	36028 KB	Ok
91	Correct	1183 ms	36028 KB	Ok
92	Correct	1288 ms	36028 KB	Ok
93	Correct	1351 ms	36028 KB	Ok
94	Correct	1289 ms	36028 KB	Ok
95	Correct	950 ms	36028 KB	Ok
96	Correct	1952 ms	36028 KB	Ok
97	Correct	1394 ms	36028 KB	Ok
98	Correct	872 ms	36028 KB	Ok
99	Correct	866 ms	36028 KB	Ok
100	Correct	1302 ms	36028 KB	Ok
101	Correct	958 ms	36028 KB	Ok
102	Correct	1395 ms	36028 KB	Ok
103	Correct	1412 ms	36028 KB	Ok
104	Correct	1452 ms	36028 KB	Ok
105	Execution timed out	2053 ms	36028 KB	Time limit exceeded
106	Halted	0 ms	0 KB	-

답안 #41502

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 9.0 / 9.0

Subtask #3 14.0 / 14.0

Subtask #4 15.0 / 15.0

Subtask #5 14.0 / 14.0

Subtask #6 18.0 / 18.0

Subtask #7 0 / 24.0

Subtask #1
6.0 / 6.0

Subtask #2
9.0 / 9.0

Subtask #3
14.0 / 14.0

Subtask #4
15.0 / 15.0

Subtask #5
14.0 / 14.0

Subtask #6
18.0 / 18.0

Subtask #7
0 / 24.0