oj.uz

Submission #909921

# Submission time Handle Problem Language Result Execution time Memory
909921 2024-01-17T15:31:06 Z daoquanglinh2007 Nice sequence (IZhO18_sequence) C++17
20 / 100
 2000 ms 4700 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]+LIM;
		dfs(u-N);
	}
	if (u+M <= k){
		sum[u+M] = sum[u]+LIM;
		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));
		for (int i = 0; i <= k; i++)
			if (!vis[i]){
				sum[i] = 0;
				dfs(i);
			}
		cout << k << '\n';
		for (int i = 1; i <= k; i++){
			cout << (sum[i]-sum[i-1] == 0 ? 1 : sum[i]-sum[i-1]) << ' ';
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 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 Correct 16 ms 2652 KB Ok
7 Incorrect 348 ms 3316 KB Expected int32, but "4248000000" found
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Ok
2 Correct 1 ms 344 KB Ok
3 Correct 1 ms 2648 KB Ok
4 Correct 1 ms 2652 KB Ok
5 Correct 1 ms 2648 KB Ok
6 Correct 1 ms 2652 KB Ok
7 Correct 1 ms 2652 KB Ok
8 Correct 1 ms 2652 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 2648 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 2049 ms 4700 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 1 ms 344 KB Ok
12 Correct 1 ms 344 KB Ok
13 Correct 1 ms 2652 KB Ok
14 Correct 1 ms 344 KB Ok
15 Correct 1 ms 2648 KB Ok
16 Correct 1 ms 2652 KB Ok
17 Correct 1 ms 2648 KB Ok
18 Correct 1 ms 2652 KB Ok
19 Correct 1 ms 2652 KB Ok
20 Correct 1 ms 2652 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 Correct 2 ms 2652 KB Ok
26 Correct 2 ms 2652 KB Ok
27 Correct 2 ms 2652 KB Ok
28 Correct 2 ms 2648 KB Ok
29 Correct 2 ms 2652 KB Ok
30 Correct 2 ms 2652 KB Ok
31 Correct 2 ms 2652 KB Ok
32 Correct 2 ms 2652 KB Ok
33 Correct 3 ms 2908 KB Ok
34 Incorrect 4 ms 2908 KB Absolute value of 1111000000 bigger than 1000000
35 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 1 ms 344 KB Ok
12 Correct 1 ms 344 KB Ok
13 Correct 1 ms 2648 KB Ok
14 Correct 1 ms 2652 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 16 ms 2652 KB Ok
19 Incorrect 348 ms 3316 KB Expected int32, but "4248000000" found
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 KB Ok
3 Correct 0 ms 348 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 1 ms 344 KB Ok
12 Correct 1 ms 344 KB Ok
13 Correct 1 ms 2648 KB Ok
14 Correct 1 ms 2652 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 16 ms 2652 KB Ok
19 Incorrect 348 ms 3316 KB Expected int32, but "4248000000" found
20 Halted 0 ms 0 KB -