結果
問題 |
No.3073 Fraction Median
|
ユーザー |
|
提出日時 | 2025-03-21 22:18:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,234 ms / 2,500 ms |
コード長 | 1,091 bytes |
コンパイル時間 | 2,551 ms |
コンパイル使用メモリ | 199,696 KB |
実行使用メモリ | 14,996 KB |
最終ジャッジ日時 | 2025-03-21 22:19:02 |
合計ジャッジ時間 | 20,073 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> istream& operator >> (istream& is, vector<T>& vec) { for(T& x : vec) is >> x; return is; } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; vector<ll> a(n); cin >> a; sort(a.begin(), a.end()); ll r = n * (n - 1) / 2; auto f = [&](long double v){ ll res = 0; for(int i = 0, j = 0; i < n; i++){ while(j < n && a[j] <= v * a[i]) j++; res += j; } return res; }; long double ng = 0, ok = 1000000005, mid; for(int i = 0; i < 128; i++){ mid = (ng + ok) / 2; (f(mid) >= r ? ok : ng) = mid; } pair<ll,ll> ans{1'000'000'009ll, 1}; for(int i = 0, j = 0; i < n; i++){ while(j < n && a[j] <= ng * a[i]) j++; if(j < n && a[j] * ans.second < a[i] * ans.first){ ans = {a[j], a[i]}; } } ll g = gcd(ans.first, ans.second); ans.first /= g; ans.second /= g; cout << ans.first << ' ' << ans.second << '\n'; }