oj.uz

Submission #789553

# Submission time Handle Problem Language Result Execution time Memory
789553 2023-07-21T13:35:08 Z temporary_juggernaut Nice sequence (IZhO18_sequence) C++14
100 / 100
 874 ms 43584 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n, m;
int timer, len;
bool used[400005];
int pref[400005];
void dfs(int v){
	used[v] = true;
	{
		int to = v - m;
		if(to >= 0 && !used[to])
			dfs(to);
	}
	{
		int to = v + n;
		if(to <= len && !used[to])
			dfs(to);
	}
	pref[v] = timer++;
}
bool check(int len){
	::len = len;
	fill(pref, pref + len + 1, 0);
	fill(used, used + len + 1, false);
	timer = 0;
	for(int i = 0; i <= len; i++)
		if(!used[i])
			dfs(i);
	for(int i = n; i <= len; i++)
		if(pref[i] - pref[i - n] > 0)
			return false;
	for(int i = m; i <= len; i++)
		if(pref[i] - pref[i - m] < 0)
			return false;
	return true;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin >> tests;
	while(tests--){
		cin >> n >> m;
		int l = 0, r = n + m;
		while(l < r){
			int mid = (l + r + 1) >> 1;
			if(check(mid))l = mid;
			else r = mid - 1;
		}
		check(l);
		cout << l << '\n';
		if(l){
			for(int i = 1; i <= l; i++)
				cout << pref[i] - pref[i - 1] << ' ';
			cout << '\n';
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 292 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 212 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 0 ms 328 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 2 ms 460 KB Ok
7 Correct 10 ms 996 KB Ok
8 Correct 5 ms 596 KB Ok
9 Correct 11 ms 1108 KB Ok
10 Correct 7 ms 724 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Ok
2 Correct 0 ms 328 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 3 ms 212 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 332 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 111 ms 9192 KB Ok
7 Correct 111 ms 9460 KB Ok
8 Correct 223 ms 12436 KB Ok
9 Correct 147 ms 11032 KB Ok
10 Correct 72 ms 5324 KB Ok
11 Correct 118 ms 10896 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 292 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 324 KB Ok
14 Correct 0 ms 328 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 3 ms 212 KB Ok
19 Correct 1 ms 212 KB Ok
20 Correct 1 ms 212 KB Ok
21 Correct 1 ms 212 KB Ok
22 Correct 1 ms 212 KB Ok
23 Correct 0 ms 332 KB Ok
24 Correct 2 ms 340 KB Ok
25 Correct 2 ms 340 KB Ok
26 Correct 2 ms 340 KB Ok
27 Correct 2 ms 340 KB Ok
28 Correct 2 ms 340 KB Ok
29 Correct 2 ms 324 KB Ok
30 Correct 2 ms 340 KB Ok
31 Correct 2 ms 340 KB Ok
32 Correct 2 ms 356 KB Ok
33 Correct 2 ms 340 KB Ok
34 Correct 5 ms 468 KB Ok
35 Correct 5 ms 580 KB Ok
36 Correct 5 ms 612 KB Ok
37 Correct 4 ms 596 KB Ok
38 Correct 4 ms 596 KB Ok
39 Correct 4 ms 596 KB Ok
40 Correct 5 ms 596 KB Ok
41 Correct 4 ms 596 KB Ok
42 Correct 5 ms 588 KB Ok
43 Correct 5 ms 596 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 292 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 0 ms 328 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 2 ms 460 KB Ok
19 Correct 10 ms 996 KB Ok
20 Correct 5 ms 596 KB Ok
21 Correct 11 ms 1108 KB Ok
22 Correct 7 ms 724 KB Ok
23 Correct 1 ms 324 KB Ok
24 Correct 0 ms 328 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 340 KB Ok
28 Correct 3 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 0 ms 332 KB Ok
34 Correct 2 ms 340 KB Ok
35 Correct 2 ms 340 KB Ok
36 Correct 2 ms 340 KB Ok
37 Correct 2 ms 340 KB Ok
38 Correct 2 ms 340 KB Ok
39 Correct 2 ms 324 KB Ok
40 Correct 2 ms 340 KB Ok
41 Correct 2 ms 340 KB Ok
42 Correct 2 ms 356 KB Ok
43 Correct 2 ms 340 KB Ok
44 Correct 5 ms 468 KB Ok
45 Correct 5 ms 580 KB Ok
46 Correct 5 ms 612 KB Ok
47 Correct 4 ms 596 KB Ok
48 Correct 4 ms 596 KB Ok
49 Correct 4 ms 596 KB Ok
50 Correct 5 ms 596 KB Ok
51 Correct 4 ms 596 KB Ok
52 Correct 5 ms 588 KB Ok
53 Correct 5 ms 596 KB Ok
54 Correct 86 ms 2384 KB Ok
55 Correct 93 ms 2720 KB Ok
56 Correct 90 ms 2768 KB Ok
57 Correct 63 ms 1960 KB Ok
58 Correct 75 ms 2152 KB Ok
59 Correct 71 ms 2104 KB Ok
60 Correct 62 ms 1888 KB Ok
61 Correct 64 ms 2052 KB Ok
62 Correct 87 ms 2508 KB Ok
63 Correct 69 ms 2104 KB Ok
64 Correct 91 ms 2764 KB Ok
65 Correct 80 ms 2380 KB Ok
66 Correct 74 ms 2164 KB Ok
67 Correct 66 ms 2108 KB Ok
68 Correct 75 ms 2236 KB Ok
69 Correct 168 ms 9872 KB Ok
70 Correct 165 ms 10444 KB Ok
71 Correct 164 ms 9936 KB Ok
72 Correct 172 ms 9804 KB Ok
73 Correct 158 ms 9932 KB Ok
74 Correct 164 ms 9788 KB Ok
75 Correct 184 ms 9388 KB Ok
76 Correct 172 ms 10180 KB Ok
77 Correct 182 ms 9504 KB Ok
78 Correct 164 ms 9952 KB Ok
79 Correct 171 ms 10060 KB Ok
80 Correct 165 ms 10144 KB Ok
81 Correct 182 ms 10052 KB Ok
82 Correct 168 ms 10020 KB Ok
83 Correct 162 ms 9424 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Ok
2 Correct 1 ms 324 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 292 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 332 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 328 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 0 ms 328 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 2 ms 460 KB Ok
19 Correct 10 ms 996 KB Ok
20 Correct 5 ms 596 KB Ok
21 Correct 11 ms 1108 KB Ok
22 Correct 7 ms 724 KB Ok
23 Correct 1 ms 324 KB Ok
24 Correct 0 ms 328 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 340 KB Ok
28 Correct 3 ms 212 KB Ok
29 Correct 1 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 0 ms 332 KB Ok
34 Correct 1 ms 328 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 111 ms 9192 KB Ok
40 Correct 111 ms 9460 KB Ok
41 Correct 223 ms 12436 KB Ok
42 Correct 147 ms 11032 KB Ok
43 Correct 72 ms 5324 KB Ok
44 Correct 118 ms 10896 KB Ok
45 Correct 2 ms 340 KB Ok
46 Correct 2 ms 340 KB Ok
47 Correct 2 ms 340 KB Ok
48 Correct 2 ms 340 KB Ok
49 Correct 2 ms 340 KB Ok
50 Correct 2 ms 324 KB Ok
51 Correct 2 ms 340 KB Ok
52 Correct 2 ms 340 KB Ok
53 Correct 2 ms 356 KB Ok
54 Correct 2 ms 340 KB Ok
55 Correct 5 ms 468 KB Ok
56 Correct 5 ms 580 KB Ok
57 Correct 5 ms 612 KB Ok
58 Correct 4 ms 596 KB Ok
59 Correct 4 ms 596 KB Ok
60 Correct 4 ms 596 KB Ok
61 Correct 5 ms 596 KB Ok
62 Correct 4 ms 596 KB Ok
63 Correct 5 ms 588 KB Ok
64 Correct 5 ms 596 KB Ok
65 Correct 86 ms 2384 KB Ok
66 Correct 93 ms 2720 KB Ok
67 Correct 90 ms 2768 KB Ok
68 Correct 63 ms 1960 KB Ok
69 Correct 75 ms 2152 KB Ok
70 Correct 71 ms 2104 KB Ok
71 Correct 62 ms 1888 KB Ok
72 Correct 64 ms 2052 KB Ok
73 Correct 87 ms 2508 KB Ok
74 Correct 69 ms 2104 KB Ok
75 Correct 91 ms 2764 KB Ok
76 Correct 80 ms 2380 KB Ok
77 Correct 74 ms 2164 KB Ok
78 Correct 66 ms 2108 KB Ok
79 Correct 75 ms 2236 KB Ok
80 Correct 168 ms 9872 KB Ok
81 Correct 165 ms 10444 KB Ok
82 Correct 164 ms 9936 KB Ok
83 Correct 172 ms 9804 KB Ok
84 Correct 158 ms 9932 KB Ok
85 Correct 164 ms 9788 KB Ok
86 Correct 184 ms 9388 KB Ok
87 Correct 172 ms 10180 KB Ok
88 Correct 182 ms 9504 KB Ok
89 Correct 164 ms 9952 KB Ok
90 Correct 171 ms 10060 KB Ok
91 Correct 165 ms 10144 KB Ok
92 Correct 182 ms 10052 KB Ok
93 Correct 168 ms 10020 KB Ok
94 Correct 162 ms 9424 KB Ok
95 Correct 199 ms 5828 KB Ok
96 Correct 279 ms 7624 KB Ok
97 Correct 274 ms 6888 KB Ok
98 Correct 202 ms 5720 KB Ok
99 Correct 288 ms 6316 KB Ok
100 Correct 265 ms 6372 KB Ok
101 Correct 262 ms 6716 KB Ok
102 Correct 252 ms 6648 KB Ok
103 Correct 250 ms 6840 KB Ok
104 Correct 296 ms 7884 KB Ok
105 Correct 278 ms 7564 KB Ok
106 Correct 249 ms 7272 KB Ok
107 Correct 296 ms 7140 KB Ok
108 Correct 309 ms 7876 KB Ok
109 Correct 283 ms 7764 KB Ok
110 Correct 771 ms 39800 KB Ok
111 Correct 770 ms 42460 KB Ok
112 Correct 774 ms 42284 KB Ok
113 Correct 760 ms 41604 KB Ok
114 Correct 775 ms 43584 KB Ok
115 Correct 782 ms 41384 KB Ok
116 Correct 874 ms 42676 KB Ok
117 Correct 783 ms 41304 KB Ok
118 Correct 729 ms 41340 KB Ok
119 Correct 774 ms 41420 KB Ok
120 Correct 757 ms 41052 KB Ok
121 Correct 741 ms 39736 KB Ok
122 Correct 755 ms 42188 KB Ok
123 Correct 749 ms 42540 KB Ok
124 Correct 814 ms 40016 KB Ok
125 Correct 806 ms 24776 KB Ok