oj.uz

Submission #909912

# Submission time Handle Problem Language Result Execution time Memory
909912 2024-01-17T15:18:46 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){
		int x = get_rand(-LIM, -1), y = get_rand(1, LIM);
		for (int j = 1; j <= k; j++)
			if (find_set(j) == j){
				f[j] = (get_rand(0, 1) ? x : y);
			}
		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 1 ms 344 KB Ok
2 Correct 1 ms 600 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 360 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 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 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 4444 KB Ok
3 Correct 2 ms 4444 KB Ok
4 Correct 1 ms 4444 KB Ok
5 Correct 1 ms 4444 KB Ok
6 Correct 116 ms 4440 KB Ok
7 Execution timed out 2016 ms 4800 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 4440 KB Ok
2 Correct 1 ms 348 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 1 ms 4444 KB Ok
7 Correct 1 ms 4444 KB Ok
8 Correct 1 ms 4440 KB Ok
9 Correct 1 ms 4444 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 4696 KB Ok
2 Correct 1 ms 4444 KB Ok
3 Correct 4 ms 4440 KB Ok
4 Correct 3 ms 4444 KB Ok
5 Correct 6 ms 4440 KB Ok
6 Execution timed out 2063 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 1 ms 344 KB Ok
2 Correct 1 ms 600 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 360 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 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 1 ms 4440 KB Ok
14 Correct 1 ms 348 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 1 ms 4444 KB Ok
19 Correct 1 ms 4444 KB Ok
20 Correct 1 ms 4440 KB Ok
21 Correct 1 ms 4444 KB Ok
22 Correct 1 ms 4444 KB Ok
23 Correct 1 ms 4444 KB Ok
24 Correct 262 ms 4676 KB Ok
25 Correct 1128 ms 4692 KB Ok
26 Correct 958 ms 4680 KB Ok
27 Execution timed out 2021 ms 4696 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 600 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 360 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 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 1 ms 4444 KB Ok
14 Correct 1 ms 4444 KB Ok
15 Correct 2 ms 4444 KB Ok
16 Correct 1 ms 4444 KB Ok
17 Correct 1 ms 4444 KB Ok
18 Correct 116 ms 4440 KB Ok
19 Execution timed out 2016 ms 4800 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Ok
2 Correct 1 ms 600 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 360 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 348 KB Ok
9 Correct 1 ms 344 KB Ok
10 Correct 1 ms 344 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 1 ms 4444 KB Ok
14 Correct 1 ms 4444 KB Ok
15 Correct 2 ms 4444 KB Ok
16 Correct 1 ms 4444 KB Ok
17 Correct 1 ms 4444 KB Ok
18 Correct 116 ms 4440 KB Ok
19 Execution timed out 2016 ms 4800 KB Time limit exceeded
20 Halted 0 ms 0 KB -