Submission #1754029
Source Code Expand
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define D(n, retu) \
REP(i, n) { cin >> retu[i]; }
#define mod 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
typedef tuple<double, ll, ll> doublep;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
for (auto &i : arr) {
fill_all(i, v);
}
}
#define yo 100001
//------------------変数-----------------------//
ll m, k;
//-------------------関数----------------------//
ll gcd(ll a, ll b) {
if (a == 0 || b == 0) {
return 0;
}
while (a % b) {
a = a % b;
swap(a, b);
}
return b;
}
int main() {
cin >> m >> k;
set<tuple<double, ll, ll>> db;
FOR(i, 2, m + 1) {
doublep a = doublep(double(1.0 / (double)i), 1, i);
db.insert(a);
}
ll itr = 0;
while (db.size()) {
itr++;
if (itr == k) {
auto hoge = db.begin();
ll a, b, c;
a = get<0>(*hoge);
b = get<1>(*hoge);
c = get<2>(*hoge);
cout << b << " " << c << endl;
return 0;
}
auto hoge = db.begin();
db.erase(db.begin());
ll a, b, c;
a = get<0>(*hoge);
b = get<1>(*hoge);
c = get<2>(*hoge);
while ((b + 1) < c) {
if (gcd(b + 1, c) == 1) {
break;
}
b++;
}
if (b + 1 >= c) {
continue;
}
if (double(1.0 / (double)c) * (double)(b + 1) < 1.0) {
doublep y = doublep(double(1.0 / (double)c) * (double)(b + 1), b + 1, c);
db.insert(y);
}
}
cout << -1 << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
fraction - 分数 (Fraction) |
User |
keidaroo |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2154 Byte |
Status |
AC |
Exec Time |
69 ms |
Memory |
2176 KB |
Judge Result
Set Name |
Set01 |
Set02 |
Set03 |
Set04 |
Set05 |
Score / Max Score |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
Set01 |
01, 02, 03 |
Set02 |
04, 05 |
Set03 |
06, 07, 08 |
Set04 |
09, 10 |
Set05 |
11, 12 |
Case Name |
Status |
Exec Time |
Memory |
01 |
AC |
2 ms |
256 KB |
02 |
AC |
2 ms |
256 KB |
03 |
AC |
2 ms |
256 KB |
04 |
AC |
2 ms |
512 KB |
05 |
AC |
2 ms |
512 KB |
06 |
AC |
59 ms |
256 KB |
07 |
AC |
5 ms |
896 KB |
08 |
AC |
50 ms |
1152 KB |
09 |
AC |
68 ms |
1536 KB |
10 |
AC |
68 ms |
1792 KB |
11 |
AC |
69 ms |
2176 KB |
12 |
AC |
68 ms |
2176 KB |