답안 #341745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341745	2020-12-30T20:29:47 Z	Tosic	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2000 ms	18896 KB

sequence

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

int n, m, t, prefS[maxn], res[maxn], ans;
vector<int> topV;
bool was[maxn];

void topSort(int x, int mx){
	// prefS[x+n] < prefS[x], prefS[x-m] < prefS[x]
	was[x] = 1;
	if(x+n <= mx and !was[x+n]){
		topSort(x+n, mx);
	}
	if(x-m >= 0 and !was[x-m]){
		topSort(x-m, mx);
	}
	topV.push_back(x);
}

bool ok(int mx){
	topV.clear();
	for(int i = 0; i <= mx; ++i){
		//cerr << was[i] << ' ';
		if(!was[i]){
			topSort(i, mx);
		}
	}
	for(int i = 0; i <= mx; ++i){
		prefS[topV[i]] = i;
		was[i] = 0;
	}
	for(int i = 0; i <= mx; ++i){
		if( (i+n<=mx and prefS[i] < prefS[i+n]) or (i-m >= 0 and prefS[i-m] > prefS[i]) ){
			return 0;
		}
	}
	for(int i = 1 ;i <mx+1;++i){
		res[i] = prefS[i]-prefS[i-1];
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> t;
	while(t--){
		cin >> n >> m;
		ans = 0;
		int l = 0, r = maxn;
		while(l <= r){
			int mid = (l+r)/2;
			//cerr<<mid<<'\n';
			if(ok(mid)){
				l=mid+1;
				ans = max(ans, mid);
			} else {
				r = mid-1;
			}
		}
		cout << ans<<'\n';
		for(int i = 1; i <= ans; ++i){
			cout << res[i] << ' ';
		}
		cout << '\n';
	}
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	4460 KB	Ok
2	Correct	26 ms	4460 KB	Ok
3	Correct	23 ms	1644 KB	Ok
4	Correct	24 ms	1516 KB	Ok
5	Correct	24 ms	1516 KB	Ok
6	Correct	24 ms	2156 KB	Ok
7	Correct	24 ms	1516 KB	Ok
8	Correct	26 ms	2156 KB	Ok
9	Correct	24 ms	1388 KB	Ok
10	Correct	24 ms	2924 KB	Ok
11	Correct	23 ms	1516 KB	Ok
12	Correct	23 ms	1388 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	2924 KB	Ok
2	Correct	25 ms	2924 KB	Ok
3	Correct	25 ms	2924 KB	Ok
4	Correct	24 ms	2924 KB	Ok
5	Correct	26 ms	2924 KB	Ok
6	Correct	28 ms	3052 KB	Ok
7	Correct	45 ms	3564 KB	Ok
8	Correct	33 ms	3180 KB	Ok
9	Correct	47 ms	3584 KB	Ok
10	Correct	38 ms	3308 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	4460 KB	Ok
2	Correct	25 ms	4460 KB	Ok
3	Correct	24 ms	2924 KB	Ok
4	Correct	23 ms	2412 KB	Ok
5	Correct	26 ms	4460 KB	Ok
6	Correct	26 ms	4460 KB	Ok
7	Correct	25 ms	4460 KB	Ok
8	Correct	25 ms	4460 KB	Ok
9	Correct	29 ms	4460 KB	Ok
10	Correct	25 ms	2924 KB	Ok
11	Correct	23 ms	2412 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	2924 KB	Ok
2	Correct	23 ms	1772 KB	Ok
3	Correct	23 ms	1644 KB	Ok
4	Correct	24 ms	1516 KB	Ok
5	Correct	23 ms	1516 KB	Ok
6	Correct	281 ms	10856 KB	Ok
7	Correct	267 ms	11388 KB	Ok
8	Correct	518 ms	14312 KB	Ok
9	Correct	369 ms	12648 KB	Ok
10	Correct	208 ms	6760 KB	Ok
11	Correct	324 ms	12804 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	4460 KB	Ok
2	Correct	26 ms	4460 KB	Ok
3	Correct	23 ms	1644 KB	Ok
4	Correct	24 ms	1516 KB	Ok
5	Correct	24 ms	1516 KB	Ok
6	Correct	24 ms	2156 KB	Ok
7	Correct	24 ms	1516 KB	Ok
8	Correct	26 ms	2156 KB	Ok
9	Correct	24 ms	1388 KB	Ok
10	Correct	24 ms	2924 KB	Ok
11	Correct	23 ms	1516 KB	Ok
12	Correct	23 ms	1388 KB	Ok
13	Correct	11 ms	4460 KB	Ok
14	Correct	25 ms	4460 KB	Ok
15	Correct	24 ms	2924 KB	Ok
16	Correct	23 ms	2412 KB	Ok
17	Correct	26 ms	4460 KB	Ok
18	Correct	26 ms	4460 KB	Ok
19	Correct	25 ms	4460 KB	Ok
20	Correct	25 ms	4460 KB	Ok
21	Correct	29 ms	4460 KB	Ok
22	Correct	25 ms	2924 KB	Ok
23	Correct	23 ms	2412 KB	Ok
24	Correct	26 ms	1388 KB	Ok
25	Correct	27 ms	1388 KB	Ok
26	Correct	27 ms	1388 KB	Ok
27	Correct	26 ms	1388 KB	Ok
28	Correct	26 ms	1480 KB	Ok
29	Correct	25 ms	1388 KB	Ok
30	Correct	25 ms	1388 KB	Ok
31	Correct	26 ms	1388 KB	Ok
32	Correct	27 ms	1388 KB	Ok
33	Correct	26 ms	1456 KB	Ok
34	Correct	34 ms	1644 KB	Ok
35	Correct	33 ms	1644 KB	Ok
36	Correct	34 ms	1644 KB	Ok
37	Correct	33 ms	1644 KB	Ok
38	Correct	32 ms	1644 KB	Ok
39	Correct	33 ms	1644 KB	Ok
40	Correct	34 ms	1644 KB	Ok
41	Correct	33 ms	1644 KB	Ok
42	Correct	33 ms	1644 KB	Ok
43	Correct	33 ms	1644 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	4460 KB	Ok
2	Correct	26 ms	4460 KB	Ok
3	Correct	23 ms	1644 KB	Ok
4	Correct	24 ms	1516 KB	Ok
5	Correct	24 ms	1516 KB	Ok
6	Correct	24 ms	2156 KB	Ok
7	Correct	24 ms	1516 KB	Ok
8	Correct	26 ms	2156 KB	Ok
9	Correct	24 ms	1388 KB	Ok
10	Correct	24 ms	2924 KB	Ok
11	Correct	23 ms	1516 KB	Ok
12	Correct	23 ms	1388 KB	Ok
13	Correct	24 ms	2924 KB	Ok
14	Correct	25 ms	2924 KB	Ok
15	Correct	25 ms	2924 KB	Ok
16	Correct	24 ms	2924 KB	Ok
17	Correct	26 ms	2924 KB	Ok
18	Correct	28 ms	3052 KB	Ok
19	Correct	45 ms	3564 KB	Ok
20	Correct	33 ms	3180 KB	Ok
21	Correct	47 ms	3584 KB	Ok
22	Correct	38 ms	3308 KB	Ok
23	Correct	11 ms	4460 KB	Ok
24	Correct	25 ms	4460 KB	Ok
25	Correct	24 ms	2924 KB	Ok
26	Correct	23 ms	2412 KB	Ok
27	Correct	26 ms	4460 KB	Ok
28	Correct	26 ms	4460 KB	Ok
29	Correct	25 ms	4460 KB	Ok
30	Correct	25 ms	4460 KB	Ok
31	Correct	29 ms	4460 KB	Ok
32	Correct	25 ms	2924 KB	Ok
33	Correct	23 ms	2412 KB	Ok
34	Correct	26 ms	1388 KB	Ok
35	Correct	27 ms	1388 KB	Ok
36	Correct	27 ms	1388 KB	Ok
37	Correct	26 ms	1388 KB	Ok
38	Correct	26 ms	1480 KB	Ok
39	Correct	25 ms	1388 KB	Ok
40	Correct	25 ms	1388 KB	Ok
41	Correct	26 ms	1388 KB	Ok
42	Correct	27 ms	1388 KB	Ok
43	Correct	26 ms	1456 KB	Ok
44	Correct	34 ms	1644 KB	Ok
45	Correct	33 ms	1644 KB	Ok
46	Correct	34 ms	1644 KB	Ok
47	Correct	33 ms	1644 KB	Ok
48	Correct	32 ms	1644 KB	Ok
49	Correct	33 ms	1644 KB	Ok
50	Correct	34 ms	1644 KB	Ok
51	Correct	33 ms	1644 KB	Ok
52	Correct	33 ms	1644 KB	Ok
53	Correct	33 ms	1644 KB	Ok
54	Correct	205 ms	3436 KB	Ok
55	Correct	231 ms	3752 KB	Ok
56	Correct	227 ms	3692 KB	Ok
57	Correct	167 ms	3052 KB	Ok
58	Correct	202 ms	3180 KB	Ok
59	Correct	188 ms	3052 KB	Ok
60	Correct	167 ms	2924 KB	Ok
61	Correct	173 ms	3052 KB	Ok
62	Correct	221 ms	3468 KB	Ok
63	Correct	197 ms	3180 KB	Ok
64	Correct	224 ms	3692 KB	Ok
65	Correct	203 ms	3308 KB	Ok
66	Correct	190 ms	3180 KB	Ok
67	Correct	171 ms	3180 KB	Ok
68	Correct	193 ms	3308 KB	Ok
69	Correct	376 ms	10864 KB	Ok
70	Correct	401 ms	11440 KB	Ok
71	Correct	364 ms	10860 KB	Ok
72	Correct	388 ms	10732 KB	Ok
73	Correct	367 ms	10924 KB	Ok
74	Correct	367 ms	10836 KB	Ok
75	Correct	378 ms	10348 KB	Ok
76	Correct	385 ms	11116 KB	Ok
77	Correct	358 ms	10456 KB	Ok
78	Correct	391 ms	10964 KB	Ok
79	Correct	374 ms	11076 KB	Ok
80	Correct	372 ms	11116 KB	Ok
81	Correct	365 ms	10988 KB	Ok
82	Correct	397 ms	10988 KB	Ok
83	Correct	353 ms	10512 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	4460 KB	Ok
2	Correct	26 ms	4460 KB	Ok
3	Correct	23 ms	1644 KB	Ok
4	Correct	24 ms	1516 KB	Ok
5	Correct	24 ms	1516 KB	Ok
6	Correct	24 ms	2156 KB	Ok
7	Correct	24 ms	1516 KB	Ok
8	Correct	26 ms	2156 KB	Ok
9	Correct	24 ms	1388 KB	Ok
10	Correct	24 ms	2924 KB	Ok
11	Correct	23 ms	1516 KB	Ok
12	Correct	23 ms	1388 KB	Ok
13	Correct	24 ms	2924 KB	Ok
14	Correct	25 ms	2924 KB	Ok
15	Correct	25 ms	2924 KB	Ok
16	Correct	24 ms	2924 KB	Ok
17	Correct	26 ms	2924 KB	Ok
18	Correct	28 ms	3052 KB	Ok
19	Correct	45 ms	3564 KB	Ok
20	Correct	33 ms	3180 KB	Ok
21	Correct	47 ms	3584 KB	Ok
22	Correct	38 ms	3308 KB	Ok
23	Correct	11 ms	4460 KB	Ok
24	Correct	25 ms	4460 KB	Ok
25	Correct	24 ms	2924 KB	Ok
26	Correct	23 ms	2412 KB	Ok
27	Correct	26 ms	4460 KB	Ok
28	Correct	26 ms	4460 KB	Ok
29	Correct	25 ms	4460 KB	Ok
30	Correct	25 ms	4460 KB	Ok
31	Correct	29 ms	4460 KB	Ok
32	Correct	25 ms	2924 KB	Ok
33	Correct	23 ms	2412 KB	Ok
34	Correct	24 ms	2924 KB	Ok
35	Correct	23 ms	1772 KB	Ok
36	Correct	23 ms	1644 KB	Ok
37	Correct	24 ms	1516 KB	Ok
38	Correct	23 ms	1516 KB	Ok
39	Correct	281 ms	10856 KB	Ok
40	Correct	267 ms	11388 KB	Ok
41	Correct	518 ms	14312 KB	Ok
42	Correct	369 ms	12648 KB	Ok
43	Correct	208 ms	6760 KB	Ok
44	Correct	324 ms	12804 KB	Ok
45	Correct	26 ms	1388 KB	Ok
46	Correct	27 ms	1388 KB	Ok
47	Correct	27 ms	1388 KB	Ok
48	Correct	26 ms	1388 KB	Ok
49	Correct	26 ms	1480 KB	Ok
50	Correct	25 ms	1388 KB	Ok
51	Correct	25 ms	1388 KB	Ok
52	Correct	26 ms	1388 KB	Ok
53	Correct	27 ms	1388 KB	Ok
54	Correct	26 ms	1456 KB	Ok
55	Correct	34 ms	1644 KB	Ok
56	Correct	33 ms	1644 KB	Ok
57	Correct	34 ms	1644 KB	Ok
58	Correct	33 ms	1644 KB	Ok
59	Correct	32 ms	1644 KB	Ok
60	Correct	33 ms	1644 KB	Ok
61	Correct	34 ms	1644 KB	Ok
62	Correct	33 ms	1644 KB	Ok
63	Correct	33 ms	1644 KB	Ok
64	Correct	33 ms	1644 KB	Ok
65	Correct	205 ms	3436 KB	Ok
66	Correct	231 ms	3752 KB	Ok
67	Correct	227 ms	3692 KB	Ok
68	Correct	167 ms	3052 KB	Ok
69	Correct	202 ms	3180 KB	Ok
70	Correct	188 ms	3052 KB	Ok
71	Correct	167 ms	2924 KB	Ok
72	Correct	173 ms	3052 KB	Ok
73	Correct	221 ms	3468 KB	Ok
74	Correct	197 ms	3180 KB	Ok
75	Correct	224 ms	3692 KB	Ok
76	Correct	203 ms	3308 KB	Ok
77	Correct	190 ms	3180 KB	Ok
78	Correct	171 ms	3180 KB	Ok
79	Correct	193 ms	3308 KB	Ok
80	Correct	376 ms	10864 KB	Ok
81	Correct	401 ms	11440 KB	Ok
82	Correct	364 ms	10860 KB	Ok
83	Correct	388 ms	10732 KB	Ok
84	Correct	367 ms	10924 KB	Ok
85	Correct	367 ms	10836 KB	Ok
86	Correct	378 ms	10348 KB	Ok
87	Correct	385 ms	11116 KB	Ok
88	Correct	358 ms	10456 KB	Ok
89	Correct	391 ms	10964 KB	Ok
90	Correct	374 ms	11076 KB	Ok
91	Correct	372 ms	11116 KB	Ok
92	Correct	365 ms	10988 KB	Ok
93	Correct	397 ms	10988 KB	Ok
94	Correct	353 ms	10512 KB	Ok
95	Execution timed out	2065 ms	18896 KB	Time limit exceeded
96	Halted	0 ms	0 KB	-

답안 #341745

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