oj.uz

Submission #909927

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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int get_rand(int l, int r){
	int tmp = rng()%(r-l+1);
	if (tmp < 0) tmp += r-l+1;
	return l + tmp;
}

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;
		while (true){
			for (int i = 0; i <= k; i++) vis[i] = 0;
			for (int i = 0; i <= k; i++)
				if (!vis[i]){
					sum[i] = get_rand(-LIM, LIM);
					dfs(i);
				}
			bool ok = 1;
			for (int i = 1; i <= k; i++)
				if (sum[i] == sum[i-1]) ok = 0;
			if (ok) break;
		}
		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 344 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 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 0 ms 348 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 16 ms 2396 KB Ok
7 Correct 333 ms 3100 KB Ok
8 Correct 99 ms 2696 KB Ok
9 Correct 310 ms 3060 KB Ok
10 Correct 161 ms 2956 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2512 KB Ok
5 Correct 3 ms 2392 KB Ok
6 Execution timed out 2058 ms 5212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.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 344 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 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 0 ms 348 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 348 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 1 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 1 ms 2396 KB Ok
19 Correct 1 ms 2396 KB Ok
20 Correct 1 ms 2392 KB Ok
21 Correct 1 ms 2396 KB Ok
22 Correct 1 ms 2396 KB Ok
23 Correct 2 ms 2396 KB Ok
24 Correct 2 ms 2396 KB Ok
25 Correct 2 ms 2396 KB Ok
26 Correct 2 ms 2396 KB Ok
27 Correct 2 ms 2396 KB Ok
28 Correct 2 ms 2396 KB Ok
29 Correct 2 ms 2396 KB Ok
30 Correct 1 ms 2396 KB Ok
31 Correct 2 ms 2396 KB Ok
32 Correct 2 ms 2396 KB Ok
33 Correct 2 ms 2392 KB Ok
34 Correct 4 ms 2620 KB Ok
35 Correct 4 ms 2652 KB Ok
36 Correct 8 ms 2632 KB Ok
37 Correct 5 ms 2652 KB Ok
38 Correct 4 ms 2652 KB Ok
39 Correct 3 ms 2652 KB Ok
40 Correct 6 ms 2652 KB Ok
41 Correct 4 ms 2692 KB Ok
42 Correct 4 ms 2652 KB Ok
43 Correct 4 ms 2652 KB Ok

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 344 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 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 0 ms 348 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 1 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 16 ms 2396 KB Ok
19 Correct 333 ms 3100 KB Ok
20 Correct 99 ms 2696 KB Ok
21 Correct 310 ms 3060 KB Ok
22 Correct 161 ms 2956 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 1 ms 348 KB Ok
25 Correct 1 ms 2396 KB Ok
26 Correct 1 ms 2396 KB Ok
27 Correct 1 ms 2396 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 1 ms 2396 KB Ok
30 Correct 1 ms 2392 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 1 ms 2396 KB Ok
33 Correct 2 ms 2396 KB Ok
34 Correct 2 ms 2396 KB Ok
35 Correct 2 ms 2396 KB Ok
36 Correct 2 ms 2396 KB Ok
37 Correct 2 ms 2396 KB Ok
38 Correct 2 ms 2396 KB Ok
39 Correct 2 ms 2396 KB Ok
40 Correct 1 ms 2396 KB Ok
41 Correct 2 ms 2396 KB Ok
42 Correct 2 ms 2396 KB Ok
43 Correct 2 ms 2392 KB Ok
44 Correct 4 ms 2620 KB Ok
45 Correct 4 ms 2652 KB Ok
46 Correct 8 ms 2632 KB Ok
47 Correct 5 ms 2652 KB Ok
48 Correct 4 ms 2652 KB Ok
49 Correct 3 ms 2652 KB Ok
50 Correct 6 ms 2652 KB Ok
51 Correct 4 ms 2692 KB Ok
52 Correct 4 ms 2652 KB Ok
53 Correct 4 ms 2652 KB Ok
54 Correct 58 ms 6976 KB Ok
55 Correct 64 ms 8276 KB Ok
56 Correct 61 ms 7704 KB Ok
57 Correct 39 ms 6100 KB Ok
58 Correct 49 ms 7384 KB Ok
59 Correct 48 ms 7192 KB Ok
60 Correct 40 ms 5972 KB Ok
61 Correct 44 ms 6372 KB Ok
62 Correct 63 ms 8608 KB Ok
63 Correct 44 ms 6320 KB Ok
64 Correct 55 ms 8016 KB Ok
65 Correct 56 ms 7732 KB Ok
66 Correct 47 ms 6996 KB Ok
67 Correct 43 ms 5972 KB Ok
68 Correct 48 ms 7060 KB Ok
69 Correct 571 ms 10564 KB Ok
70 Correct 344 ms 10576 KB Ok
71 Correct 460 ms 11348 KB Ok
72 Execution timed out 2092 ms 7328 KB Time limit exceeded
73 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 344 KB Ok
4 Correct 1 ms 348 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 1 ms 344 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 0 ms 348 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 1 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 16 ms 2396 KB Ok
19 Correct 333 ms 3100 KB Ok
20 Correct 99 ms 2696 KB Ok
21 Correct 310 ms 3060 KB Ok
22 Correct 161 ms 2956 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 1 ms 348 KB Ok
25 Correct 1 ms 2396 KB Ok
26 Correct 1 ms 2396 KB Ok
27 Correct 1 ms 2396 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 1 ms 2396 KB Ok
30 Correct 1 ms 2392 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 1 ms 2396 KB Ok
33 Correct 2 ms 2396 KB Ok
34 Correct 1 ms 2396 KB Ok
35 Correct 1 ms 2396 KB Ok
36 Correct 1 ms 2396 KB Ok
37 Correct 1 ms 2512 KB Ok
38 Correct 3 ms 2392 KB Ok
39 Execution timed out 2058 ms 5212 KB Time limit exceeded
40 Halted 0 ms 0 KB -