結果

問題 No.5020 Averaging
コンテスト
ユーザー Tekyla
提出日時 2026-05-28 21:33:52
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 1,884 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,375 ms
コンパイル使用メモリ 192,340 KB
実行使用メモリ 6,400 KB
スコア 0
最終ジャッジ日時 2026-05-28 21:34:02
合計ジャッジ時間 6,880 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

//const LOCAL_EXECUTE:bool = true;
const TARGET: i64 = 500_000_000_000_000_000;
const OPERATION_LIMIT: usize = 50;

fn operatioin(u: usize, v: usize, ab: &mut [(i64, i64)]) {
    let (a1, b1) = ab[u];
    let (a2, b2) = ab[v];
    let am = (a1 + a2) / 2;
    let bm = (b1 + b2) / 2;
    ab[u] = (am, bm);
    ab[v] = (am, bm);
}

fn calc_score(mut ab: Vec<(i64, i64)>, op: &[(usize, usize)]) -> i64 {
    for &(u, v) in op {
        operatioin(u, v, &mut ab);
    }
    let (a, b) = ab[0];
    let v1 = a.abs_diff(TARGET);
    let v2 = b.abs_diff(TARGET);
    let m = v1.max(v2);
    let x = op.len() as i64;
    if m == 0 {
        return 2000050 - x;
    }
    let score = 2000000.0 - 100000.0 * f64::log10(m as f64 + 1.0);
    score as i64
}

fn solver1(n: usize, mut ab: Vec<(i64, i64)>) -> Vec<(usize, usize)> {
    // いったん全部の平均に近づくようにやってみる
    // a_max - a_min と b_max - b_min の一番大きな組み合わせのカードで平均を取る
    let mut ans = vec![];
    for _ in 0..OPERATION_LIMIT {
        let mut dist_max = -1;
        let mut i = 0;
        let mut j = 0;
        for ii in 0..(n - 1) {
            let (ai, bi) = ab[ii];
            for jj in (ii + 1)..n {
                let (aj, bj) = ab[jj];
                let dist = (ai - aj).abs().max((bi - bj).abs());
                if dist > dist_max {
                    dist_max = dist;
                    i = ii;
                    j = jj
                }
            }
        }
        ans.push((i, j));
        operatioin(i, j, &mut ab);
    }
    ans
}

fn main() {
    input! {
        n:usize,
        ab:[(i64, i64); n]
    }
    // solve
    let ans = solver1(n, ab.clone());
    eprintln!("{}", calc_score(ab.clone(), &ans));
    println!("{}", ans.len());
    for &(u,v) in &ans{
        println!("{} {}", u, v);
    } 
    
}
0