oj.uz

Submission #507933

# Submission time Handle Problem Language Result Execution time Memory
507933 2022-01-13T04:40:17 Z Mazaalai Nice sequence (IZhO18_sequence) C++17
100 / 100
 1474 ms 56776 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
int n, m, mul, k, lim;
int arr[2*N], curVal;
bool vis[2*N], possible;
void solve(int pos) {
	if (arr[pos] != 0) return;
	if (vis[pos]) {
		possible = 0;
		return;
	}
	vis[pos] = 1;
	if (possible && pos+m <= lim) solve(pos+m);
	if (possible && pos-n >= 0) solve(pos-n);
	arr[pos] = curVal++;
}
void go() {
	cin >> n >> m;
	vector <int> ans(1, 1);
	k = max(n, m);
	int l = k-1, r = n+m-1;
	while(l <= r) {
		int mid = (l+r)>>1;
		curVal = possible = 1;
		for (int i = 0; i < 2*k+5; i++) 
			arr[i] = vis[i] = 0;
		lim = mid;
		for (int i = 0; i <= mid && possible; i++) {
			if (vis[i]) continue;
			solve(i);
		}
		if (!possible) {
			r = mid-1;
		} else {
			l = mid+1;
			vector <int> cur;
			for (int i = 1; i <= mid; i++) cur.pb(arr[i] - arr[i-1]);
			ans = cur;
		}
	}
	cout << ans.size() << '\n';
	for (auto el : ans) cout << -el << ' '; cout << '\n';

}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	int T;
	cin >> T;
	while(T--) go();
}

Compilation message

sequence.cpp: In function 'void go()':
sequence.cpp:44:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 |  for (auto el : ans) cout << -el << ' '; cout << '\n';
      |  ^~~
sequence.cpp:44:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 |  for (auto el : ans) cout << -el << ' '; cout << '\n';
      |                                          ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 328 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 312 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 308 KB Ok
12 Correct 1 ms 204 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 308 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 2 ms 460 KB Ok
7 Correct 8 ms 1228 KB Ok
8 Correct 4 ms 716 KB Ok
9 Correct 11 ms 1500 KB Ok
10 Correct 5 ms 844 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 0 ms 204 KB Ok
3 Correct 0 ms 320 KB Ok
4 Correct 0 ms 332 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 211 ms 13584 KB Ok
7 Correct 163 ms 14924 KB Ok
8 Correct 344 ms 17956 KB Ok
9 Correct 337 ms 17520 KB Ok
10 Correct 165 ms 9476 KB Ok
11 Correct 328 ms 17648 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 328 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 312 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 308 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 0 ms 332 KB Ok
14 Correct 1 ms 324 KB Ok
15 Correct 0 ms 332 KB Ok
16 Correct 0 ms 204 KB Ok
17 Correct 0 ms 204 KB Ok
18 Correct 0 ms 204 KB Ok
19 Correct 0 ms 204 KB Ok
20 Correct 0 ms 204 KB Ok
21 Correct 0 ms 328 KB Ok
22 Correct 1 ms 204 KB Ok
23 Correct 0 ms 204 KB Ok
24 Correct 2 ms 432 KB Ok
25 Correct 2 ms 460 KB Ok
26 Correct 2 ms 460 KB Ok
27 Correct 2 ms 460 KB Ok
28 Correct 2 ms 332 KB Ok
29 Correct 3 ms 460 KB Ok
30 Correct 3 ms 320 KB Ok
31 Correct 2 ms 452 KB Ok
32 Correct 2 ms 324 KB Ok
33 Correct 2 ms 332 KB Ok
34 Correct 6 ms 716 KB Ok
35 Correct 7 ms 716 KB Ok
36 Correct 6 ms 712 KB Ok
37 Correct 6 ms 704 KB Ok
38 Correct 6 ms 716 KB Ok
39 Correct 6 ms 716 KB Ok
40 Correct 6 ms 676 KB Ok
41 Correct 7 ms 692 KB Ok
42 Correct 7 ms 748 KB Ok
43 Correct 6 ms 708 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 328 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 312 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 308 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 1 ms 308 KB Ok
15 Correct 1 ms 332 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 2 ms 460 KB Ok
19 Correct 8 ms 1228 KB Ok
20 Correct 4 ms 716 KB Ok
21 Correct 11 ms 1500 KB Ok
22 Correct 5 ms 844 KB Ok
23 Correct 0 ms 332 KB Ok
24 Correct 1 ms 324 KB Ok
25 Correct 0 ms 332 KB Ok
26 Correct 0 ms 204 KB Ok
27 Correct 0 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 0 ms 204 KB Ok
30 Correct 0 ms 204 KB Ok
31 Correct 0 ms 328 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 204 KB Ok
34 Correct 2 ms 432 KB Ok
35 Correct 2 ms 460 KB Ok
36 Correct 2 ms 460 KB Ok
37 Correct 2 ms 460 KB Ok
38 Correct 2 ms 332 KB Ok
39 Correct 3 ms 460 KB Ok
40 Correct 3 ms 320 KB Ok
41 Correct 2 ms 452 KB Ok
42 Correct 2 ms 324 KB Ok
43 Correct 2 ms 332 KB Ok
44 Correct 6 ms 716 KB Ok
45 Correct 7 ms 716 KB Ok
46 Correct 6 ms 712 KB Ok
47 Correct 6 ms 704 KB Ok
48 Correct 6 ms 716 KB Ok
49 Correct 6 ms 716 KB Ok
50 Correct 6 ms 676 KB Ok
51 Correct 7 ms 692 KB Ok
52 Correct 7 ms 748 KB Ok
53 Correct 6 ms 708 KB Ok
54 Correct 86 ms 4288 KB Ok
55 Correct 92 ms 5032 KB Ok
56 Correct 100 ms 4532 KB Ok
57 Correct 66 ms 3760 KB Ok
58 Correct 127 ms 4444 KB Ok
59 Correct 80 ms 4168 KB Ok
60 Correct 79 ms 3760 KB Ok
61 Correct 61 ms 3772 KB Ok
62 Correct 139 ms 4704 KB Ok
63 Correct 95 ms 4004 KB Ok
64 Correct 121 ms 4996 KB Ok
65 Correct 97 ms 4608 KB Ok
66 Correct 80 ms 4512 KB Ok
67 Correct 75 ms 4108 KB Ok
68 Correct 107 ms 4348 KB Ok
69 Correct 267 ms 13072 KB Ok
70 Correct 276 ms 13216 KB Ok
71 Correct 285 ms 12808 KB Ok
72 Correct 243 ms 12764 KB Ok
73 Correct 273 ms 13124 KB Ok
74 Correct 233 ms 13364 KB Ok
75 Correct 234 ms 12736 KB Ok
76 Correct 264 ms 12988 KB Ok
77 Correct 236 ms 13340 KB Ok
78 Correct 253 ms 12752 KB Ok
79 Correct 267 ms 13240 KB Ok
80 Correct 237 ms 12892 KB Ok
81 Correct 294 ms 13236 KB Ok
82 Correct 268 ms 12976 KB Ok
83 Correct 258 ms 13484 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 1 ms 328 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 1 ms 332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 312 KB Ok
10 Correct 1 ms 204 KB Ok
11 Correct 1 ms 308 KB Ok
12 Correct 1 ms 204 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 1 ms 308 KB Ok
15 Correct 1 ms 332 KB Ok
16 Correct 1 ms 204 KB Ok
17 Correct 1 ms 204 KB Ok
18 Correct 2 ms 460 KB Ok
19 Correct 8 ms 1228 KB Ok
20 Correct 4 ms 716 KB Ok
21 Correct 11 ms 1500 KB Ok
22 Correct 5 ms 844 KB Ok
23 Correct 0 ms 332 KB Ok
24 Correct 1 ms 324 KB Ok
25 Correct 0 ms 332 KB Ok
26 Correct 0 ms 204 KB Ok
27 Correct 0 ms 204 KB Ok
28 Correct 0 ms 204 KB Ok
29 Correct 0 ms 204 KB Ok
30 Correct 0 ms 204 KB Ok
31 Correct 0 ms 328 KB Ok
32 Correct 1 ms 204 KB Ok
33 Correct 0 ms 204 KB Ok
34 Correct 0 ms 204 KB Ok
35 Correct 0 ms 204 KB Ok
36 Correct 0 ms 320 KB Ok
37 Correct 0 ms 332 KB Ok
38 Correct 1 ms 332 KB Ok
39 Correct 211 ms 13584 KB Ok
40 Correct 163 ms 14924 KB Ok
41 Correct 344 ms 17956 KB Ok
42 Correct 337 ms 17520 KB Ok
43 Correct 165 ms 9476 KB Ok
44 Correct 328 ms 17648 KB Ok
45 Correct 2 ms 432 KB Ok
46 Correct 2 ms 460 KB Ok
47 Correct 2 ms 460 KB Ok
48 Correct 2 ms 460 KB Ok
49 Correct 2 ms 332 KB Ok
50 Correct 3 ms 460 KB Ok
51 Correct 3 ms 320 KB Ok
52 Correct 2 ms 452 KB Ok
53 Correct 2 ms 324 KB Ok
54 Correct 2 ms 332 KB Ok
55 Correct 6 ms 716 KB Ok
56 Correct 7 ms 716 KB Ok
57 Correct 6 ms 712 KB Ok
58 Correct 6 ms 704 KB Ok
59 Correct 6 ms 716 KB Ok
60 Correct 6 ms 716 KB Ok
61 Correct 6 ms 676 KB Ok
62 Correct 7 ms 692 KB Ok
63 Correct 7 ms 748 KB Ok
64 Correct 6 ms 708 KB Ok
65 Correct 86 ms 4288 KB Ok
66 Correct 92 ms 5032 KB Ok
67 Correct 100 ms 4532 KB Ok
68 Correct 66 ms 3760 KB Ok
69 Correct 127 ms 4444 KB Ok
70 Correct 80 ms 4168 KB Ok
71 Correct 79 ms 3760 KB Ok
72 Correct 61 ms 3772 KB Ok
73 Correct 139 ms 4704 KB Ok
74 Correct 95 ms 4004 KB Ok
75 Correct 121 ms 4996 KB Ok
76 Correct 97 ms 4608 KB Ok
77 Correct 80 ms 4512 KB Ok
78 Correct 75 ms 4108 KB Ok
79 Correct 107 ms 4348 KB Ok
80 Correct 267 ms 13072 KB Ok
81 Correct 276 ms 13216 KB Ok
82 Correct 285 ms 12808 KB Ok
83 Correct 243 ms 12764 KB Ok
84 Correct 273 ms 13124 KB Ok
85 Correct 233 ms 13364 KB Ok
86 Correct 234 ms 12736 KB Ok
87 Correct 264 ms 12988 KB Ok
88 Correct 236 ms 13340 KB Ok
89 Correct 253 ms 12752 KB Ok
90 Correct 267 ms 13240 KB Ok
91 Correct 237 ms 12892 KB Ok
92 Correct 294 ms 13236 KB Ok
93 Correct 268 ms 12976 KB Ok
94 Correct 258 ms 13484 KB Ok
95 Correct 214 ms 9712 KB Ok
96 Correct 343 ms 16696 KB Ok
97 Correct 276 ms 11932 KB Ok
98 Correct 248 ms 11748 KB Ok
99 Correct 266 ms 13160 KB Ok
100 Correct 296 ms 13968 KB Ok
101 Correct 281 ms 14392 KB Ok
102 Correct 256 ms 14340 KB Ok
103 Correct 272 ms 13848 KB Ok
104 Correct 368 ms 14776 KB Ok
105 Correct 297 ms 15080 KB Ok
106 Correct 277 ms 13128 KB Ok
107 Correct 343 ms 15276 KB Ok
108 Correct 338 ms 16540 KB Ok
109 Correct 252 ms 13228 KB Ok
110 Correct 1171 ms 54220 KB Ok
111 Correct 1288 ms 53332 KB Ok
112 Correct 1217 ms 54428 KB Ok
113 Correct 1225 ms 51896 KB Ok
114 Correct 1441 ms 56776 KB Ok
115 Correct 1414 ms 53348 KB Ok
116 Correct 1409 ms 53904 KB Ok
117 Correct 1474 ms 53084 KB Ok
118 Correct 1325 ms 56732 KB Ok
119 Correct 1335 ms 52388 KB Ok
120 Correct 1351 ms 52872 KB Ok
121 Correct 1292 ms 52932 KB Ok
122 Correct 1310 ms 53592 KB Ok
123 Correct 1306 ms 53436 KB Ok
124 Correct 1125 ms 54512 KB Ok
125 Correct 1335 ms 37624 KB Ok