oj.uz

Submission #792386

# Submission time Handle Problem Language Result Execution time Memory
792386 2023-07-25T04:00:37 Z 1075508020060209tc Euklid (COCI20_euklid) C++14
35 / 110
 1000 ms 131888 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: 'int' and 'std::vector<std::pair<int, 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 667 ms 131724 KB Output is correct
2 Correct 672 ms 131708 KB Output is correct
3 Correct 678 ms 131760 KB Output is correct
4 Correct 669 ms 131672 KB Output is correct
5 Correct 680 ms 131736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 131744 KB Output is correct
2 Correct 676 ms 131720 KB Output is correct
3 Correct 668 ms 131764 KB Output is correct
4 Correct 669 ms 131668 KB Output is correct
5 Correct 681 ms 131760 KB Output is correct
6 Correct 689 ms 131728 KB Output is correct
7 Correct 671 ms 131716 KB Output is correct
8 Correct 680 ms 131808 KB Output is correct
9 Correct 675 ms 131720 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 131800 KB Output is correct
2 Correct 673 ms 131736 KB Output is correct
3 Correct 666 ms 131636 KB Output is correct
4 Correct 670 ms 131712 KB Output is correct
5 Correct 681 ms 131684 KB Output is correct
6 Correct 675 ms 131692 KB Output is correct
7 Correct 682 ms 131680 KB Output is correct
8 Correct 671 ms 131664 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 131696 KB Output is correct
2 Correct 678 ms 131752 KB Output is correct
3 Correct 676 ms 131668 KB Output is correct
4 Correct 670 ms 131744 KB Output is correct
5 Correct 676 ms 131728 KB Output is correct
6 Correct 672 ms 131748 KB Output is correct
7 Correct 673 ms 131736 KB Output is correct
8 Correct 672 ms 131752 KB Output is correct
9 Correct 674 ms 131776 KB Output is correct
10 Correct 673 ms 131728 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 131696 KB Output is correct
2 Correct 678 ms 131752 KB Output is correct
3 Correct 676 ms 131668 KB Output is correct
4 Correct 670 ms 131744 KB Output is correct
5 Correct 676 ms 131728 KB Output is correct
6 Correct 672 ms 131748 KB Output is correct
7 Correct 673 ms 131736 KB Output is correct
8 Correct 672 ms 131752 KB Output is correct
9 Correct 674 ms 131776 KB Output is correct
10 Correct 673 ms 131728 KB Output is correct
11 Correct 676 ms 131888 KB Output is correct
12 Execution timed out 1077 ms 131712 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 131724 KB Output is correct
2 Correct 672 ms 131708 KB Output is correct
3 Correct 678 ms 131760 KB Output is correct
4 Correct 669 ms 131672 KB Output is correct
5 Correct 680 ms 131736 KB Output is correct
6 Correct 670 ms 131744 KB Output is correct
7 Correct 676 ms 131720 KB Output is correct
8 Correct 668 ms 131764 KB Output is correct
9 Correct 669 ms 131668 KB Output is correct
10 Correct 681 ms 131760 KB Output is correct
11 Correct 689 ms 131728 KB Output is correct
12 Correct 671 ms 131716 KB Output is correct
13 Correct 680 ms 131808 KB Output is correct
14 Correct 675 ms 131720 KB Output is correct
15 Correct 671 ms 131800 KB Output is correct
16 Correct 673 ms 131736 KB Output is correct
17 Correct 666 ms 131636 KB Output is correct
18 Correct 670 ms 131712 KB Output is correct
19 Correct 681 ms 131684 KB Output is correct
20 Correct 675 ms 131692 KB Output is correct
21 Correct 682 ms 131680 KB Output is correct
22 Correct 671 ms 131664 KB Output is correct
23 Correct 683 ms 131696 KB Output is correct
24 Correct 678 ms 131752 KB Output is correct
25 Correct 676 ms 131668 KB Output is correct
26 Correct 670 ms 131744 KB Output is correct
27 Correct 676 ms 131728 KB Output is correct
28 Correct 672 ms 131748 KB Output is correct
29 Correct 673 ms 131736 KB Output is correct
30 Correct 672 ms 131752 KB Output is correct
31 Correct 674 ms 131776 KB Output is correct
32 Correct 673 ms 131728 KB Output is correct
33 Correct 676 ms 131888 KB Output is correct
34 Execution timed out 1077 ms 131712 KB Time limit exceeded
35 Halted 0 ms 0 KB -