Submission #872155

# Submission time Handle Problem Language Result Execution time Memory
872155 2023-11-12T11:42:43 Z Onur_Ilgaz Euklid (COCI20_euklid) C++17
75 / 110
46 ms 3672 KB
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = ((int)1e8) / 4;

void solve(){
	int g, h;
	cin >> g >> h;
	bitset <N> dp; // if(dp[i]) then we can get R'(i, h)
	dp[1] = 1;
	for(int i = 1; i < N; i++) {
		if(!dp[i]) continue;
		if(i >= g) {
			int a = i, b = h; // a >= b garantili
			// cout << a << " " << b << "\n";
			// cout << a << " " << b << "\n";
			// b'yi g'nin katı yapacağız
			int need = (g - (a * b % g)) % g;
			b = a * b + need;
			// b artık g'nin katı
			// cout << a << " " << b << "\n";
			swap(a, b);
			if(gcd(a, b) == g) {
				cout << a << " " << b << "\n\n";
				return;
			}
			// a >= b garantili
			// a % g == 0 garantili
			b = a * b + ((a == g) ? 0 : g);
			cout << a << " " << b << "\n\n";
			return;
		}
		for(int j = 0; j < h and i * h + j < N; j++) {
			dp[i * h + j] = 1;
		}
	}
	exit(1);
}

int32_t main(){
	fast
	int t=1;
	cin>>t;
	while(t--) solve();
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3416 KB Output is correct
2 Correct 14 ms 3416 KB Output is correct
3 Correct 4 ms 3420 KB Output is correct
4 Correct 15 ms 3508 KB Output is correct
5 Correct 11 ms 3392 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 37 ms 3420 KB Output is correct
4 Correct 37 ms 3420 KB Output is correct
5 Correct 12 ms 3420 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 5 ms 3500 KB Output is correct
8 Correct 5 ms 3420 KB Output is correct
9 Correct 8 ms 3420 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3416 KB Output is correct
2 Correct 13 ms 3420 KB Output is correct
3 Correct 11 ms 3420 KB Output is correct
4 Correct 9 ms 3504 KB Output is correct
5 Correct 8 ms 3420 KB Output is correct
6 Correct 6 ms 3420 KB Output is correct
7 Correct 5 ms 3444 KB Output is correct
8 Correct 5 ms 3508 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3500 KB Output is correct
3 Correct 4 ms 3416 KB Output is correct
4 Correct 6 ms 3672 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 4 ms 3504 KB Output is correct
9 Correct 4 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3500 KB Output is correct
3 Correct 4 ms 3416 KB Output is correct
4 Correct 6 ms 3672 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 4 ms 3504 KB Output is correct
9 Correct 4 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 20 ms 3504 KB Output is correct
13 Correct 19 ms 3420 KB Output is correct
14 Correct 7 ms 3504 KB Output is correct
15 Correct 16 ms 3504 KB Output is correct
16 Correct 5 ms 3504 KB Output is correct
17 Correct 46 ms 3348 KB Output is correct
18 Correct 5 ms 3416 KB Output is correct
19 Correct 6 ms 3420 KB Output is correct
20 Correct 6 ms 3420 KB Output is correct
21 Correct 5 ms 3416 KB Output is correct
22 Correct 5 ms 3420 KB Output is correct
23 Correct 4 ms 3420 KB Output is correct
24 Correct 4 ms 3420 KB Output is correct
25 Correct 5 ms 3420 KB Output is correct
26 Correct 5 ms 3420 KB Output is correct
27 Correct 6 ms 3500 KB Output is correct
28 Correct 3 ms 3420 KB Output is correct
29 Correct 2 ms 3420 KB Output is correct
30 Correct 14 ms 3420 KB Output is correct
31 Correct 4 ms 3420 KB Output is correct
32 Correct 8 ms 3504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 3416 KB Output is correct
2 Correct 14 ms 3416 KB Output is correct
3 Correct 4 ms 3420 KB Output is correct
4 Correct 15 ms 3508 KB Output is correct
5 Correct 11 ms 3392 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 37 ms 3420 KB Output is correct
9 Correct 37 ms 3420 KB Output is correct
10 Correct 12 ms 3420 KB Output is correct
11 Correct 5 ms 3420 KB Output is correct
12 Correct 5 ms 3500 KB Output is correct
13 Correct 5 ms 3420 KB Output is correct
14 Correct 8 ms 3420 KB Output is correct
15 Correct 4 ms 3416 KB Output is correct
16 Correct 13 ms 3420 KB Output is correct
17 Correct 11 ms 3420 KB Output is correct
18 Correct 9 ms 3504 KB Output is correct
19 Correct 8 ms 3420 KB Output is correct
20 Correct 6 ms 3420 KB Output is correct
21 Correct 5 ms 3444 KB Output is correct
22 Correct 5 ms 3508 KB Output is correct
23 Correct 4 ms 3420 KB Output is correct
24 Correct 4 ms 3500 KB Output is correct
25 Correct 4 ms 3416 KB Output is correct
26 Correct 6 ms 3672 KB Output is correct
27 Correct 4 ms 3420 KB Output is correct
28 Correct 4 ms 3420 KB Output is correct
29 Correct 4 ms 3420 KB Output is correct
30 Correct 4 ms 3504 KB Output is correct
31 Correct 4 ms 3420 KB Output is correct
32 Correct 4 ms 3420 KB Output is correct
33 Correct 3 ms 3420 KB Output is correct
34 Correct 20 ms 3504 KB Output is correct
35 Correct 19 ms 3420 KB Output is correct
36 Correct 7 ms 3504 KB Output is correct
37 Correct 16 ms 3504 KB Output is correct
38 Correct 5 ms 3504 KB Output is correct
39 Correct 46 ms 3348 KB Output is correct
40 Correct 5 ms 3416 KB Output is correct
41 Correct 6 ms 3420 KB Output is correct
42 Correct 6 ms 3420 KB Output is correct
43 Correct 5 ms 3416 KB Output is correct
44 Correct 5 ms 3420 KB Output is correct
45 Correct 4 ms 3420 KB Output is correct
46 Correct 4 ms 3420 KB Output is correct
47 Correct 5 ms 3420 KB Output is correct
48 Correct 5 ms 3420 KB Output is correct
49 Correct 6 ms 3500 KB Output is correct
50 Correct 3 ms 3420 KB Output is correct
51 Correct 2 ms 3420 KB Output is correct
52 Correct 14 ms 3420 KB Output is correct
53 Correct 4 ms 3420 KB Output is correct
54 Correct 8 ms 3504 KB Output is correct
55 Runtime error 25 ms 3416 KB Execution failed because the return code was nonzero
56 Halted 0 ms 0 KB -