oj.uz

Submission #374501

# Submission time Handle Problem Language Result Execution time Memory
374501 2021-03-07T10:43:58 Z topovik Euklid (COCI20_euklid) C++14
20 / 110
 1000 ms 35008 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 2e3 + 100;

ll gcd[N][N];

ll f(ll x, ll y)
{
    if (x < y) swap(x, y);
    if (y == 1) return x;
    else return f(x / y, y);
}

int main()
{
    for (ll i = 1; i < N; i++)
        for (ll j = 1; j < N; j++) gcd[i][j] = __gcd(i, j);
    ll t;
    cin >> t;
    while (t--)
    {
        ll x, y;
        cin >> x >> y;
        if (x == y)
        {
            cout << x << " " << x << endl;
            continue;
        }
        if (y == 2)
        {
            cout << x << " " << 2 * x << endl;
            continue;
        }
        if (x == y * y)
        {
            cout << x << " " << x * y << endl;
            continue;
        }
        ll l = -1, r = -1;
        for (ll i = 1; i < N; i++)
            for (ll j = 1; j < N; j++)
              if (gcd[i][j] == 1 && f(i * x, j * x) == y) {l = i * x, r = j * x;break;}
        cout << l << " " << r << endl;
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34796 KB Output is correct
2 Correct 203 ms 34924 KB Output is correct
3 Correct 204 ms 34796 KB Output is correct
4 Correct 204 ms 34924 KB Output is correct
5 Correct 203 ms 34924 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 34796 KB Output is correct
2 Correct 203 ms 34796 KB Output is correct
3 Correct 203 ms 34796 KB Output is correct
4 Correct 202 ms 35008 KB Output is correct
5 Correct 203 ms 34924 KB Output is correct
6 Correct 200 ms 34796 KB Output is correct
7 Correct 209 ms 34924 KB Output is correct
8 Correct 202 ms 34796 KB Output is correct
9 Correct 201 ms 34796 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34796 KB Output is correct
2 Correct 203 ms 34924 KB Output is correct
3 Correct 200 ms 34796 KB Output is correct
4 Correct 202 ms 34796 KB Output is correct
5 Correct 202 ms 34924 KB Output is correct
6 Correct 202 ms 34796 KB Output is correct
7 Correct 202 ms 34796 KB Output is correct
8 Correct 212 ms 34796 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 34796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 34796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34796 KB Output is correct
2 Correct 203 ms 34924 KB Output is correct
3 Correct 204 ms 34796 KB Output is correct
4 Correct 204 ms 34924 KB Output is correct
5 Correct 203 ms 34924 KB Output is correct
6 Correct 201 ms 34796 KB Output is correct
7 Correct 203 ms 34796 KB Output is correct
8 Correct 203 ms 34796 KB Output is correct
9 Correct 202 ms 35008 KB Output is correct
10 Correct 203 ms 34924 KB Output is correct
11 Correct 200 ms 34796 KB Output is correct
12 Correct 209 ms 34924 KB Output is correct
13 Correct 202 ms 34796 KB Output is correct
14 Correct 201 ms 34796 KB Output is correct
15 Correct 202 ms 34796 KB Output is correct
16 Correct 203 ms 34924 KB Output is correct
17 Correct 200 ms 34796 KB Output is correct
18 Correct 202 ms 34796 KB Output is correct
19 Correct 202 ms 34924 KB Output is correct
20 Correct 202 ms 34796 KB Output is correct
21 Correct 202 ms 34796 KB Output is correct
22 Correct 212 ms 34796 KB Output is correct
23 Execution timed out 1032 ms 34796 KB Time limit exceeded
24 Halted 0 ms 0 KB -