結果

問題 No.3073 Fraction Median
ユーザー 👑 loop0919
提出日時 2025-03-21 23:15:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,464 bytes
コンパイル時間 1,128 ms
コンパイル使用メモリ 104,136 KB
実行使用メモリ 14,776 KB
最終ジャッジ日時 2025-03-21 23:15:22
合計ジャッジ時間 6,892 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ユーザ定義の gcd 関数（ユークリッドの互除法）
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// グローバル変数
int N;
vector<long long> A;

// __int128 を使って積の比較を安全に行う関数
bool comp(long long x_c, long long x_d, long long y_c, long long y_d) {
    __int128 lhs = (__int128)x_c * y_d;
    __int128 rhs = (__int128)y_c * x_d;
    return lhs <= rhs;
}

// check 関数: 与えられた val に対して (bool, (max_c, max_d)) を返す
pair<bool, pair<long long, long long>> check(long long val) {
    long long max_c = 0, max_d = 1;
    long long cnt = 0;
    for (int i = 0; i < N; i++) {
        int ok = 0, ng = N;
        // バイナリサーチ: 条件を満たす最大の ok を求める
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            // Python の comp((A[mid-1], A[i]), (val, 10**18)) に対応
            if (comp(A[mid - 1], A[i], val, 1000000000000000000LL)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        cnt += ok;
        // 条件により最大の分数 (max_c, max_d) を更新
        if (ok > 0 && comp(max_c, max_d, A[ok - 1], A[i])) {
            max_c = A[ok - 1];
            max_d = A[i];
        }
    }
    // ペア数が N*(N-1)/2 未満なら true、それ以外なら false を返す
    if (cnt < (long long)N * (N - 1) / 2) {
        return {true, {max_c, max_d}};
    } else {
        return {false, {max_c, max_d}};
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 入力
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    // ソート
    sort(A.begin(), A.end());
    
    // main のバイナリサーチ: [0, 10^18+1) の範囲で val を探索
    long long ok_val = 0, ng_val = 1000000000000000000LL + 1;
    while (ng_val - ok_val > 1) {
        long long mid = (ok_val + ng_val) / 2;
        if (check(mid).first) {
            ok_val = mid;
        } else {
            ng_val = mid;
        }
    }
    // 答えの分数を得る
    auto ans = check(ng_val).second;
    long long g = gcd(ans.first, ans.second);
    cout << (ans.first / g) << " " << (ans.second / g) << "\n";
    
    return 0;
}
0