oj.uz

Submission #909911

# Submission time Handle Problem Language Result Execution time Memory
909911 2024-01-17T15:17:08 Z daoquanglinh2007 Nice sequence (IZhO18_sequence) C++17
20 / 100
 2000 ms 8540 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;
int parent[NM+5], sz[NM+5], f[NM+5];
vector <int> v;
 
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 make_set(int v){
	parent[v] = v;
	sz[v] = 1;
}
 
int find_set(int v){
	return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}
 
void union_sets(int u, int v){
	u = find_set(u);
	v = find_set(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);
	parent[v] = u;
	sz[u] += sz[v];
}
 
void check(int k){
	for (int i = 1; i <= k; i++) make_set(i);
	for (int i = 1; i+N <= k; i++) union_sets(i, i+N);
	for (int i = 1; i+M <= k; i++) union_sets(i, i+M);
	
	while (true){
		for (int j = 1; j <= k; j++)
			if (find_set(j) == j){
				while (true){
					f[j] = get_rand(-LIM, LIM);
					if (f[j] != 0) break;
				}
			}
		int sum1 = 0, sum2 = 0;
		for (int j = 1; j <= k; j++){
			if (j <= N) sum1 += f[find_set(j)];
			if (j <= M) sum2 += f[find_set(j)];
		}
		if ((k < N || sum1 < 0) && (k < M || sum2 > 0)){
			v.clear();
			for (int j = 1; j <= k; j++) v.push_back(f[find_set(j)]);
			break;
		}
	}
}
 
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;
		}
		int res = N+M-__gcd(N, M)-1;
		check(res);
		
		cout << res << '\n';
		for (int x : v) cout << x << ' ';
		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 1 ms 344 KB Ok
3 Correct 1 ms 348 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 0 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Ok
2 Correct 1 ms 4440 KB Ok
3 Correct 1 ms 4440 KB Ok
4 Correct 1 ms 4444 KB Ok
5 Correct 1 ms 4444 KB Ok
6 Correct 112 ms 4608 KB Ok
7 Execution timed out 2037 ms 4692 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4488 KB Ok
2 Correct 1 ms 4440 KB Ok
3 Correct 2 ms 4440 KB Ok
4 Correct 3 ms 4444 KB Ok
5 Correct 5 ms 4444 KB Ok
6 Execution timed out 2072 ms 8540 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 1 ms 344 KB Ok
3 Correct 1 ms 348 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 0 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 4444 KB Ok
14 Correct 0 ms 348 KB Ok
15 Correct 1 ms 4444 KB Ok
16 Correct 1 ms 4444 KB Ok
17 Correct 1 ms 4444 KB Ok
18 Correct 1 ms 4444 KB Ok
19 Correct 1 ms 4444 KB Ok
20 Correct 1 ms 4444 KB Ok
21 Correct 1 ms 4440 KB Ok
22 Correct 1 ms 4444 KB Ok
23 Correct 1 ms 4444 KB Ok
24 Correct 15 ms 4700 KB Ok
25 Correct 523 ms 4700 KB Ok
26 Correct 237 ms 4680 KB Ok
27 Correct 1633 ms 4708 KB Ok
28 Correct 262 ms 4644 KB Ok
29 Execution timed out 2045 ms 4444 KB Time limit exceeded
30 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 1 ms 344 KB Ok
3 Correct 1 ms 348 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 0 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 4444 KB Ok
14 Correct 1 ms 4440 KB Ok
15 Correct 1 ms 4440 KB Ok
16 Correct 1 ms 4444 KB Ok
17 Correct 1 ms 4444 KB Ok
18 Correct 112 ms 4608 KB Ok
19 Execution timed out 2037 ms 4692 KB Time limit exceeded
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 1 ms 344 KB Ok
3 Correct 1 ms 348 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 0 ms 348 KB Ok
9 Correct 1 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 0 ms 348 KB Ok
12 Correct 0 ms 348 KB Ok
13 Correct 1 ms 4444 KB Ok
14 Correct 1 ms 4440 KB Ok
15 Correct 1 ms 4440 KB Ok
16 Correct 1 ms 4444 KB Ok
17 Correct 1 ms 4444 KB Ok
18 Correct 112 ms 4608 KB Ok
19 Execution timed out 2037 ms 4692 KB Time limit exceeded
20 Halted 0 ms 0 KB -