#1066310 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: SnowBeenDiding
• 提出日時: 2025-04-11 16:16:15
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 919 ms / 1,000 ms
• コード長: 11,281 bytes
• コンパイル時間: 13,627 ms
• コンパイル使用メモリ: 403,976 KB
• 実行使用メモリ: 7,848 KB
• スコア: 20,268,634
• 最終ジャッジ日時: 2025-04-11 16:17:18
• 合計ジャッジ時間: 59,891 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

warning: unused imports: `BufReader` and `stdin`
   --> src/main.rs:348:15
    |
348 | use std::io::{stdin, BufReader};
    |               ^^^^^  ^^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: function `card_error_max` is never used
   --> src/main.rs:166:4
    |
166 | fn card_error_max(u: (u64, u64)) -> u64 {
    |    ^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `card_error_sum` is never used
   --> src/main.rs:170:4
    |
170 | fn card_error_sum(u: (u64, u64)) -> u64 {
    |    ^^^^^^^^^^^^^^

warning: function `sign` is never used
   --> src/main.rs:194:4
    |
194 | fn sign(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> i128 {
    |    ^^^^

warning: function `point_in_triangle_i128` is never used
   --> src/main.rs:205:4
    |
205 | fn point_in_triangle_i128(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
    |    ^^^^^^^^^^^^^^^^^^^^^^

ソースコード

// -*- coding:utf-8-unix -*-

use proconio::{fastout, input};

const TARGET: u64 = 500_000_000_000_000_000;
const MINV: u64 = 100_000_000_000_000_000;
const TARGET_ADJ: u64 = TARGET - MINV;
const OP_NUM: usize = 50;

#[fastout]
fn main() {
    let _ = get_time();

    input! {
        n: usize,
        mut ab: [(u64, u64); n],
    }

    // adjust value interval
    for x in &mut ab {
        x.0 -= MINV;
        x.1 -= MINV;
    }

    let mut triangle_valuations = SegmentTree::new(
        (n - 1) * (n - 2) / 2,
        || (u64::MAX, u64::MAX, u64::MAX),
        |x, y| x.min(y),
    );
    for i in 1..n {
        for j in i + 1..n {
            triangle_valuations.update(triangle_num(i, j), triangle_val_l0(ab[0], ab[i], ab[j]));
        }
    }
    let mut ans = Vec::new();

    for _ in 0..OP_NUM {
        if get_time() >= TIME_LIMIT {
            break;
        }
        // choose 0
        let mut best_v = 0;
        let mut best_score_v = (u64::MAX, u64::MAX, u64::MAX);
        for v in 1..n {
            let old_ab0 = ab[0];
            let old_abv = ab[v];
            let new_ab = card_avg(ab[0], ab[v]);
            ab[0] = new_ab;
            ab[v] = new_ab;
            let mut score_new = (u64::MAX, u64::MAX, u64::MAX);
            for i in 1..n {
                for j in i + 1..n {
                    score_new = score_new.min(triangle_val_l0(ab[0], ab[i], ab[j]));
                }
            }

            if score_new < best_score_v {
                best_score_v = score_new;
                best_v = v;
            }

            ab[0] = old_ab0;
            ab[v] = old_abv;
        }
        // not choose 0
        let mut best_uv = (0, 0);
        let mut best_score_uv = (u64::MAX, u64::MAX, u64::MAX);
        let mut old_tr_score_u = vec![(u64::MAX, u64::MAX, u64::MAX); n];
        let mut old_tr_score_v = vec![(u64::MAX, u64::MAX, u64::MAX); n];
        for u in 1..n {
            for v in u + 1..n {
                // modify ab
                let old_abu = ab[u];
                let old_abv = ab[v];
                let new_ab = card_avg(ab[u], ab[v]);
                ab[u] = new_ab;
                ab[v] = new_ab;
                // recalc for u
                for k in 1..n {
                    if k == u {
                        continue;
                    }
                    let i = k.min(u);
                    let j = k.max(u);
                    let trnum = triangle_num(i, j);
                    old_tr_score_u[k] = triangle_valuations.query_onepoint(trnum);
                    triangle_valuations.update(trnum, triangle_val_l0(ab[0], ab[i], ab[j]));
                }
                // recalc for v
                for k in 1..n {
                    if k == v {
                        continue;
                    }
                    let i = k.min(v);
                    let j = k.max(v);
                    let trnum = triangle_num(i, j);
                    old_tr_score_v[k] = triangle_valuations.query_onepoint(trnum);
                    triangle_valuations.update(trnum, triangle_val_l0(ab[0], ab[i], ab[j]));
                }
                let thisscore = triangle_valuations.query(0..(n - 1) * (n - 2) / 2);
                if best_score_uv > thisscore {
                    best_score_uv = thisscore;
                    best_uv = (u, v);
                }
                // restore valuations
                for k in 1..n {
                    if k == u {
                        continue;
                    }
                    let i = k.min(u);
                    let j = k.max(u);
                    let trnum = triangle_num(i, j);
                    triangle_valuations.update(trnum, old_tr_score_u[k]);
                }
                for k in 1..n {
                    if k == v {
                        continue;
                    }
                    let i = k.min(v);
                    let j = k.max(v);
                    let trnum = triangle_num(i, j);
                    triangle_valuations.update(trnum, old_tr_score_v[k]);
                }
                // restore ab
                ab[u] = old_abu;
                ab[v] = old_abv;
            }
        }

        // update
        if best_score_v <= best_score_uv {
            if best_v == 0 {
                break;
            }
            ans.push((0, best_v));
            ab[0] = card_avg(ab[0], ab[best_v]);
        } else {
            if best_uv == (0, 0) {
                break;
            }
            ans.push(best_uv);
            let (u, v) = best_uv;
            let newab = card_avg(ab[u], ab[v]);
            ab[u] = newab;
            ab[v] = newab;
        }

        for i in 1..n {
            for j in i + 1..n {
                triangle_valuations
                    .update(triangle_num(i, j), triangle_val_l0(ab[0], ab[i], ab[j]));
            }
        }
    }

    println!("{}", ans.len());
    for &(u, v) in &ans {
        println!("{} {}", u + 1, v + 1);
    }
}

fn card_avg(u: (u64, u64), v: (u64, u64)) -> (u64, u64) {
    ((u.0 + v.0) / 2, (u.1 + v.1) / 2)
}

fn card_error_max(u: (u64, u64)) -> u64 {
    (u.0.abs_diff(TARGET_ADJ)).max(u.1.abs_diff(TARGET_ADJ))
}

fn card_error_sum(u: (u64, u64)) -> u64 {
    (u.0.abs_diff(TARGET_ADJ)) + (u.1.abs_diff(TARGET_ADJ))
}

fn triangle_num(u: usize, v: usize) -> usize {
    (v - 1) * (v - 2) / 2 + u - 1
}

fn triangle_val_l0(a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> (u64, u64, u64) {
    if !point_in_triangle((TARGET_ADJ, TARGET_ADJ), a, b, c) {
        return (u64::MAX, u64::MAX, u64::MAX);
    }
    let mut vals = [l0_len(a, b), l0_len(b, c), l0_len(c, a)];
    vals.sort_unstable();
    return (vals[2], vals[1], vals[0]);
}

fn l0_len(a: (u64, u64), b: (u64, u64)) -> u64 {
    a.0.abs_diff(b.0).max(a.1.abs_diff(b.1))
}

/// 3点 p1, p2, p3 の順序で作る平面上の「向き」を、クロス積の符号で返す関数
/// 計算式は (p1 - p3) × (p2 - p3) となり、
/// 正なら p3 を起点として p1->p2 が反時計回り、負なら時計回り、0 なら 3 点は同一直線上にあることを意味する。
fn sign(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> i128 {
    (p1.0 as i128 - p3.0 as i128) * (p2.1 as i128 - p3.1 as i128)
        - (p2.0 as i128 - p3.0 as i128) * (p1.1 as i128 - p3.1 as i128)
}

fn sign_f64(p1: (u64, u64), p2: (u64, u64), p3: (u64, u64)) -> f64 {
    (p1.0 as f64 - p3.0 as f64) * (p2.1 as f64 - p3.1 as f64)
        - (p2.0 as f64 - p3.0 as f64) * (p1.1 as f64 - p3.1 as f64)
}

/// 点 `pt` が、頂点 a, b, c で作られる三角形の内部（もしくは境界上）にあるかを判定する関数
fn point_in_triangle_i128(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
    // 各エッジに対して、pt の位置関係をクロス積の符号で評価する
    let d1 = sign(pt, a, b);
    let d2 = sign(pt, b, c);
    let d3 = sign(pt, c, a);

    // d1, d2, d3 のうち、負の値を持つかどうか
    let has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    // 同様に正の値が存在するか
    let has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    // すべての符号が同じ（または 0 を含む）なら pt は三角形内
    !(has_neg && has_pos)
}

fn point_in_triangle(pt: (u64, u64), a: (u64, u64), b: (u64, u64), c: (u64, u64)) -> bool {
    // 各エッジに対して、pt の位置関係をクロス積の符号で評価する
    let d1 = sign_f64(pt, a, b);
    let d2 = sign_f64(pt, b, c);
    let d3 = sign_f64(pt, c, a);

    // d1, d2, d3 のうち、負の値を持つかどうか
    let has_neg = (d1 < 0.) || (d2 < 0.) || (d3 < 0.);
    // 同様に正の値が存在するか
    let has_pos = (d1 > 0.) || (d2 > 0.) || (d3 > 0.);

    // すべての符号が同じ（または 0 を含む）なら pt は三角形内
    !(has_neg && has_pos)
}

//
// MARK: Time Measurement
//

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

#[allow(unused)]
#[cfg(debug_assertions)]
const TIME_LIMIT: f64 = 10.;

#[allow(unused)]
#[cfg(not(debug_assertions))]
const TIME_LIMIT: f64 = 0.9;

// Segment tree for range minimum query and alike problems
// The closures must fulfill the defining laws of monoids
// Indexing is 0-based
// The code is based on that in C++ in the 'ant book'
#[derive(Clone, PartialEq, Debug)]
struct SegmentTree<A, CUnit, CMult> {
    data: Vec<A>,
    monoid_unit_closure: CUnit,
    monoid_op_closure: CMult,
}

#[allow(dead_code)]
impl<A, CUnit, CMult> SegmentTree<A, CUnit, CMult>
where
    A: Copy,
    CUnit: Fn() -> A,
    CMult: Fn(A, A) -> A,
{
    fn new(n: usize, monoid_unit_closure: CUnit, monoid_op_closure: CMult) -> Self {
        let mut nn = 1;
        while nn < n {
            nn *= 2;
        }
        let this = Self {
            data: vec![monoid_unit_closure(); 2 * nn - 1],
            monoid_unit_closure,
            monoid_op_closure,
        };
        return this;
    }

    fn query_onepoint(&self, k: usize) -> A {
        let nn = (self.data.len() + 1) / 2;
        return self.data[k + nn - 1];
    }

    fn from_slice(sl: &[A], monoid_unit_closure: CUnit, monoid_op_closure: CMult) -> Self {
        let n = sl.len();
        let mut nn = 1;
        while nn < n {
            nn *= 2;
        }
        let mut data = vec![monoid_unit_closure(); 2 * nn - 1];
        for k in 0..n {
            data[k + nn - 1] = sl[k];
        }
        if n >= 2 {
            for j in (0..=(n + nn - 3) / 2).rev() {
                data[j] = (monoid_op_closure)(data[j * 2 + 1], data[j * 2 + 2]);
            }
        }
        Self {
            data,
            monoid_unit_closure,
            monoid_op_closure,
        }
    }

    fn update(&mut self, k: usize, a: A) {
        let n = (self.data.len() + 1) / 2;
        let mut k = k + n - 1;
        self.data[k] = a;
        while k > 0 {
            k = (k - 1) / 2;
            self.data[k] = (self.monoid_op_closure)(self.data[k * 2 + 1], self.data[k * 2 + 2]);
        }
    }

    fn query_internal(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> A {
        if r <= a || b <= l {
            return (self.monoid_unit_closure)();
        }
        if a <= l && r <= b {
            return self.data[k];
        } else {
            let vl = self.query_internal(a, b, k * 2 + 1, l, (l + r) / 2);
            let vr = self.query_internal(a, b, k * 2 + 2, (l + r) / 2, r);
            return (self.monoid_op_closure)(vl, vr);
        }
    }
}

trait RangeQuery<T> {
    type Output;
    fn query(&self, r: T) -> Self::Output;
}

use std::io::{stdin, BufReader};
use std::ops::Range;

#[allow(dead_code)]
impl<A, CUnit, CMult> RangeQuery<Range<usize>> for SegmentTree<A, CUnit, CMult>
where
    A: Copy,
    CUnit: Fn() -> A,
    CMult: Fn(A, A) -> A,
{
    type Output = A;
    fn query(&self, range: Range<usize>) -> A {
        let n = (self.data.len() + 1) / 2;
        return self.query_internal(range.start, range.end, 0, 0, n);
    }
}