#955308 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: tmzn
• 提出日時: 2024-02-25 14:12:59
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 982 ms / 1,000 ms
• コード長: 3,912 bytes
• コンパイル時間: 1,154 ms
• コンパイル使用メモリ: 193,504 KB
• 実行使用メモリ: 6,676 KB
• スコア: 14,792,731
• 最終ジャッジ日時: 2024-02-25 14:13:52
• 合計ジャッジ時間: 53,257 ms
• ジャッジサーバーID （参考情報）: judge10 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	980 ms; 6,676 KB
testcase_01	AC	981 ms; 6,676 KB
testcase_02	AC	981 ms; 6,676 KB
testcase_03	AC	981 ms; 6,676 KB
testcase_04	AC	981 ms; 6,676 KB
testcase_05	AC	981 ms; 6,676 KB
testcase_06	AC	981 ms; 6,676 KB
testcase_07	AC	981 ms; 6,676 KB
testcase_08	AC	981 ms; 6,676 KB
testcase_09	AC	981 ms; 6,676 KB
testcase_10	AC	981 ms; 6,676 KB
testcase_11	AC	981 ms; 6,676 KB
testcase_12	AC	981 ms; 6,676 KB
testcase_13	AC	981 ms; 6,676 KB
testcase_14	AC	981 ms; 6,676 KB
testcase_15	AC	981 ms; 6,676 KB
testcase_16	AC	981 ms; 6,676 KB
testcase_17	AC	982 ms; 6,676 KB
testcase_18	AC	981 ms; 6,676 KB
testcase_19	AC	981 ms; 6,676 KB
testcase_20	AC	982 ms; 6,676 KB
testcase_21	AC	981 ms; 6,676 KB
testcase_22	AC	981 ms; 6,676 KB
testcase_23	AC	981 ms; 6,676 KB
testcase_24	AC	981 ms; 6,676 KB
testcase_25	AC	982 ms; 6,676 KB
testcase_26	AC	981 ms; 6,676 KB
testcase_27	AC	981 ms; 6,676 KB
testcase_28	AC	981 ms; 6,676 KB
testcase_29	AC	981 ms; 6,676 KB
testcase_30	AC	981 ms; 6,676 KB
testcase_31	AC	981 ms; 6,676 KB
testcase_32	AC	981 ms; 6,676 KB
testcase_33	AC	981 ms; 6,676 KB
testcase_34	AC	981 ms; 6,676 KB
testcase_35	AC	982 ms; 6,676 KB
testcase_36	AC	981 ms; 6,676 KB
testcase_37	AC	981 ms; 6,676 KB
testcase_38	AC	982 ms; 6,676 KB
testcase_39	AC	982 ms; 6,676 KB
testcase_40	AC	981 ms; 6,676 KB
testcase_41	AC	981 ms; 6,676 KB
testcase_42	AC	981 ms; 6,676 KB
testcase_43	AC	981 ms; 6,676 KB
testcase_44	AC	981 ms; 6,676 KB
testcase_45	AC	981 ms; 6,676 KB
testcase_46	AC	981 ms; 6,676 KB
testcase_47	AC	981 ms; 6,676 KB
testcase_48	AC	981 ms; 6,676 KB
testcase_49	AC	980 ms; 6,676 KB

コンパイルメッセージ

warning: variable does not need to be mutable
   --> Main.rs:122:9
    |
122 |     let mut timer = Timer::new(0.98);
    |         ----^^^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: method `reset` is never used
  --> Main.rs:20:8
   |
12 | impl Timer {
   | ---------- method in this implementation
...
20 |     fn reset(&mut self) {
   |        ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: 2 warnings emitted

ソースコード

use std::io;

use std::time::Instant;

const ANS: usize = 500_000_000_000_000_000;

struct Timer {
    start: Instant,
    end: f64,
}

impl Timer {
    fn new(end: f64) -> Timer {
        Timer {
            start: Instant::now(),
            end,
        }
    }

    fn reset(&mut self) {
        self.start = Instant::now();
    }

    fn elapsed(&self) -> f64 {
        #[cfg(feature = "local")]
        {
            self.start.elapsed().as_secs_f64() * 2.0
        }
        #[cfg(not(feature = "local"))]
        {
            self.start.elapsed().as_secs_f64()
        }
    }

    fn is_timeout(&self) -> bool {
        self.elapsed() >= self.end
    }
}

pub struct PcgXshRr {
    state: u64,
    inc: u64,
}

impl PcgXshRr {
    // 新しい PcgXshRr インスタンスを作成するメソッド
    pub fn new(seed: u64, inc: u64) -> Self {
        let mut pcg = PcgXshRr { state: 0, inc };
        pcg.seed(seed);
        pcg
    }

    // シードを設定するメソッド
    pub fn seed(&mut self, seed: u64) {
        self.state = 0;
        self.inc = (seed << 1) | 1;
        self.next(); // 初期値を生成する
        self.state = self.state.wrapping_add(seed);
    }

    // 次の乱数を生成するメソッド
    pub fn next(&mut self) -> u64 {
        let old_state = self.state;
        self.state = old_state
            .wrapping_mul(6364136223846793005)
            .wrapping_add(self.inc);
        let xorshifted = ((old_state >> 18) ^ old_state) >> 27;
        let rot = old_state >> 59;
        (xorshifted >> rot) | (xorshifted << ((-(rot as i32)) & 31))
    }

    // 指定した範囲の乱数を生成するメソッド
    pub fn gen_range(&mut self, start: u64, end: u64) -> u64 {
        if start >= end {
            panic!("Invalid range");
        }
        start + self.next() % (end - start)
    }
}

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).expect("Failed to read line");
    let n: usize = n.trim().parse().expect("Failed to parse N");

    let mut a: Vec<(u64, u64)> = Vec::new();

    for _ in 0..n {
        let mut input = String::new();
        io::stdin()
            .read_line(&mut input)
            .expect("Failed to read line");

        let pair: Vec<u64> = input
            .split_whitespace()
            .map(|s| s.parse().expect("Failed to parse u64"))
            .collect();

        if pair.len() == 2 {
            a.push((pair[0], pair[1]));
        } else {
            panic!("Invalid input format for A_i B_i");
        }
    }

    let mut sol = vec![];
    let mut rng = PcgXshRr::new(123, 456);
    for _ in 0..50 {
        let r1 = rng.gen_range(0, 45) as usize;
        let r2 = rng.gen_range(0, 45) as usize;
        let front = ((a[r1].0 + a[r2].0) as f64 / 2f64).ceil() as u64;
        let back = ((a[r1].1 + a[r2].1) as f64 / 2f64).ceil() as u64;
        a[r1] = (front, back);
        a[r2] = (front, back);

        sol.push((r1 + 1, r2 + 1));
    }
    let mut best_score = calc_score(&sol);
    eprintln!("score = {}", best_score);

    
    let mut timer = Timer::new(0.98);
    while !timer.is_timeout() {
        let r1 = rng.gen_range(0, 50) as usize;
        let r2 = rng.gen_range(0, 50) as usize;
        let mut copy_sol = sol.clone();
        copy_sol.swap(r1, r2);
        let new_score = calc_score(&copy_sol);
        if new_score > best_score {
            best_score = new_score;
            sol = copy_sol;
            eprintln!("score = {}", best_score);
        }
    }

    println!("{}", sol.len());
    for (r1, r2) in sol {
        let r2 = if r1 == r2 { r2 + 1 } else { r2 };
        println!("{} {}", r1, r2);
    }
}

fn calc_score(sol: &[(usize, usize)]) -> usize {
    let d1 = (sol[0].0 as i32 - ANS as i32).abs();
    let d2 = (sol[0].1 as i32 - ANS as i32).abs();
    (2000000f64 - 100000f64 * (d1.max(d2) as f64 + 1f64).log10()).ceil() as usize
}