oj.uz

Submission #792385

# Submission time Handle Problem Language Result Execution time Memory
792385 2023-07-25T03:59:33 Z 1075508020060209tc Euklid (COCI20_euklid) C++14
35 / 110
 1000 ms 263168 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
//#pragma GCC target("popcnt")
using namespace std;
#define int long long
#define X first
#define Y second
int G;int H;
int ttt;
int ek(int a,int b){
if(a<b){return ek(b,a);}
if(b==1){return a;}
return ek(a/b,b);
}

vector<pair<int,int>>co;

void solve(){
cin>>G>>H;
/*
for(int i=1;i<=3000;i++){
    for(int j=1;j<=4000;j++){
        if(ek(i*G,j*G)==H&&__gcd(i,j)==1){
            cout<<i*G<<" "<<j*G<<endl;return;
        }
    }
}*/

for(int i=0;i<co.size();i++){
    int a=G*co[i].first;int b=G*co[i].second;
    if(ek(a,b)==H){
        cout<<a<<" "<<b<<endl;return;
    }
}

}
int dp[2000006];

signed main()
{

    for(int i=1;i<=4000;i++){
        for(int j=1;j<=4000;j++){
            if(__gcd(i,j)==1){
                co.push_back({i,j});
            }
        }
    }


    cin>>ttt;
    while(ttt--)solve();


}

Compilation message

euklid.cpp: In function 'void solve()':
euklid.cpp:30:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | for(int i=0;i<co.size();i++){
      |             ~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 263076 KB Output is correct
2 Correct 753 ms 263096 KB Output is correct
3 Correct 747 ms 263000 KB Output is correct
4 Correct 749 ms 263080 KB Output is correct
5 Correct 750 ms 263056 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 263044 KB Output is correct
2 Correct 745 ms 263028 KB Output is correct
3 Correct 743 ms 263016 KB Output is correct
4 Correct 761 ms 263112 KB Output is correct
5 Correct 759 ms 263072 KB Output is correct
6 Correct 753 ms 263104 KB Output is correct
7 Correct 751 ms 263084 KB Output is correct
8 Correct 748 ms 263064 KB Output is correct
9 Correct 765 ms 263048 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 263008 KB Output is correct
2 Correct 743 ms 262988 KB Output is correct
3 Correct 743 ms 263088 KB Output is correct
4 Correct 749 ms 262980 KB Output is correct
5 Correct 751 ms 263036 KB Output is correct
6 Correct 748 ms 263080 KB Output is correct
7 Correct 745 ms 263104 KB Output is correct
8 Correct 765 ms 263084 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 263128 KB Output is correct
2 Correct 762 ms 263052 KB Output is correct
3 Correct 749 ms 263044 KB Output is correct
4 Correct 750 ms 263016 KB Output is correct
5 Correct 755 ms 263004 KB Output is correct
6 Correct 751 ms 262976 KB Output is correct
7 Correct 748 ms 263080 KB Output is correct
8 Correct 767 ms 263044 KB Output is correct
9 Correct 755 ms 263168 KB Output is correct
10 Correct 758 ms 263116 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 263128 KB Output is correct
2 Correct 762 ms 263052 KB Output is correct
3 Correct 749 ms 263044 KB Output is correct
4 Correct 750 ms 263016 KB Output is correct
5 Correct 755 ms 263004 KB Output is correct
6 Correct 751 ms 262976 KB Output is correct
7 Correct 748 ms 263080 KB Output is correct
8 Correct 767 ms 263044 KB Output is correct
9 Correct 755 ms 263168 KB Output is correct
10 Correct 758 ms 263116 KB Output is correct
11 Correct 752 ms 263064 KB Output is correct
12 Execution timed out 1080 ms 262968 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 263076 KB Output is correct
2 Correct 753 ms 263096 KB Output is correct
3 Correct 747 ms 263000 KB Output is correct
4 Correct 749 ms 263080 KB Output is correct
5 Correct 750 ms 263056 KB Output is correct
6 Correct 746 ms 263044 KB Output is correct
7 Correct 745 ms 263028 KB Output is correct
8 Correct 743 ms 263016 KB Output is correct
9 Correct 761 ms 263112 KB Output is correct
10 Correct 759 ms 263072 KB Output is correct
11 Correct 753 ms 263104 KB Output is correct
12 Correct 751 ms 263084 KB Output is correct
13 Correct 748 ms 263064 KB Output is correct
14 Correct 765 ms 263048 KB Output is correct
15 Correct 748 ms 263008 KB Output is correct
16 Correct 743 ms 262988 KB Output is correct
17 Correct 743 ms 263088 KB Output is correct
18 Correct 749 ms 262980 KB Output is correct
19 Correct 751 ms 263036 KB Output is correct
20 Correct 748 ms 263080 KB Output is correct
21 Correct 745 ms 263104 KB Output is correct
22 Correct 765 ms 263084 KB Output is correct
23 Correct 760 ms 263128 KB Output is correct
24 Correct 762 ms 263052 KB Output is correct
25 Correct 749 ms 263044 KB Output is correct
26 Correct 750 ms 263016 KB Output is correct
27 Correct 755 ms 263004 KB Output is correct
28 Correct 751 ms 262976 KB Output is correct
29 Correct 748 ms 263080 KB Output is correct
30 Correct 767 ms 263044 KB Output is correct
31 Correct 755 ms 263168 KB Output is correct
32 Correct 758 ms 263116 KB Output is correct
33 Correct 752 ms 263064 KB Output is correct
34 Execution timed out 1080 ms 262968 KB Time limit exceeded
35 Halted 0 ms 0 KB -