oj.uz

Submission #909922

# Submission time Handle Problem Language Result Execution time Memory
909922 2024-01-17T15:32:46 Z daoquanglinh2007 Nice sequence (IZhO18_sequence) C++17
29 / 100
 2000 ms 4184 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define isz(a) (int)(a).size()
 
const int NM = 4e5, LIM = 1e6;
 
int T, N, M, k;
int sum[NM+5];
bool vis[NM+5];

void dfs(int u){
	vis[u] = 1;
	if (u-N >= 0){
		sum[u-N] = sum[u]+1;
		dfs(u-N);
	}
	if (u+M <= k){
		sum[u+M] = sum[u]+1;
		dfs(u+M);
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while (T--){
		cin >> N >> M;
		if (N%M == 0){
			cout << N-1 << '\n';
			for (int i = 1; i < N; i++) cout << 1 << ' ';
			cout << '\n';
			continue;
		}
		if (M%N == 0){
			cout << M-1 << '\n';
			for (int i = 1; i < M; i++) cout << -1 << ' ';
			cout << '\n';
			continue;
		}
		k = N+M-__gcd(N, M)-1;
		memset(vis, 0, sizeof(vis));
		int tmp = 0;
		for (int i = 0; i <= k; i++)
			if (!vis[i]){
				sum[i] = --tmp;
				dfs(i);
			}
		cout << k << '\n';
		for (int i = 1; i <= k; i++){
			cout << sum[i]-sum[i-1] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 344 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Ok
2 Correct 1 ms 2652 KB Ok
3 Correct 1 ms 2652 KB Ok
4 Correct 0 ms 2804 KB Ok
5 Correct 1 ms 2648 KB Ok
6 Correct 15 ms 2652 KB Ok
7 Correct 328 ms 3156 KB Ok
8 Correct 98 ms 2828 KB Ok
9 Correct 299 ms 3156 KB Ok
10 Correct 151 ms 2908 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Ok
2 Correct 1 ms 344 KB Ok
3 Correct 1 ms 2652 KB Ok
4 Correct 1 ms 2652 KB Ok
5 Correct 1 ms 2652 KB Ok
6 Correct 1 ms 2652 KB Ok
7 Correct 1 ms 2648 KB Ok
8 Correct 1 ms 2648 KB Ok
9 Correct 1 ms 2652 KB Ok
10 Correct 1 ms 2652 KB Ok
11 Correct 1 ms 2652 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Ok
2 Correct 1 ms 2652 KB Ok
3 Correct 1 ms 2652 KB Ok
4 Correct 1 ms 2652 KB Ok
5 Correct 1 ms 2652 KB Ok
6 Execution timed out 2031 ms 4184 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 344 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 2648 KB Ok
14 Correct 1 ms 344 KB Ok
15 Correct 1 ms 2652 KB Ok
16 Correct 1 ms 2652 KB Ok
17 Correct 1 ms 2652 KB Ok
18 Correct 1 ms 2652 KB Ok
19 Correct 1 ms 2648 KB Ok
20 Correct 1 ms 2648 KB Ok
21 Correct 1 ms 2652 KB Ok
22 Correct 1 ms 2652 KB Ok
23 Correct 1 ms 2652 KB Ok
24 Correct 2 ms 2648 KB Ok
25 Incorrect 2 ms 2652 KB All the numbers must be nonzero
26 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 344 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 2652 KB Ok
14 Correct 1 ms 2652 KB Ok
15 Correct 1 ms 2652 KB Ok
16 Correct 0 ms 2804 KB Ok
17 Correct 1 ms 2648 KB Ok
18 Correct 15 ms 2652 KB Ok
19 Correct 328 ms 3156 KB Ok
20 Correct 98 ms 2828 KB Ok
21 Correct 299 ms 3156 KB Ok
22 Correct 151 ms 2908 KB Ok
23 Correct 1 ms 2648 KB Ok
24 Correct 1 ms 344 KB Ok
25 Correct 1 ms 2652 KB Ok
26 Correct 1 ms 2652 KB Ok
27 Correct 1 ms 2652 KB Ok
28 Correct 1 ms 2652 KB Ok
29 Correct 1 ms 2648 KB Ok
30 Correct 1 ms 2648 KB Ok
31 Correct 1 ms 2652 KB Ok
32 Correct 1 ms 2652 KB Ok
33 Correct 1 ms 2652 KB Ok
34 Correct 2 ms 2648 KB Ok
35 Incorrect 2 ms 2652 KB All the numbers must be nonzero
36 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 348 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 1 ms 344 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 1 ms 348 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 0 ms 348 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 2652 KB Ok
14 Correct 1 ms 2652 KB Ok
15 Correct 1 ms 2652 KB Ok
16 Correct 0 ms 2804 KB Ok
17 Correct 1 ms 2648 KB Ok
18 Correct 15 ms 2652 KB Ok
19 Correct 328 ms 3156 KB Ok
20 Correct 98 ms 2828 KB Ok
21 Correct 299 ms 3156 KB Ok
22 Correct 151 ms 2908 KB Ok
23 Correct 1 ms 2648 KB Ok
24 Correct 1 ms 344 KB Ok
25 Correct 1 ms 2652 KB Ok
26 Correct 1 ms 2652 KB Ok
27 Correct 1 ms 2652 KB Ok
28 Correct 1 ms 2652 KB Ok
29 Correct 1 ms 2648 KB Ok
30 Correct 1 ms 2648 KB Ok
31 Correct 1 ms 2652 KB Ok
32 Correct 1 ms 2652 KB Ok
33 Correct 1 ms 2652 KB Ok
34 Correct 1 ms 2652 KB Ok
35 Correct 1 ms 2652 KB Ok
36 Correct 1 ms 2652 KB Ok
37 Correct 1 ms 2652 KB Ok
38 Correct 1 ms 2652 KB Ok
39 Execution timed out 2031 ms 4184 KB Time limit exceeded
40 Halted 0 ms 0 KB -