#955621 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: tmzn
• 提出日時: 2024-02-25 16:23:40
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 982 ms / 1,000 ms
• コード長: 4,088 bytes
• コンパイル時間: 842 ms
• コンパイル使用メモリ: 193,436 KB
• 実行使用メモリ: 6,548 KB
• スコア: 16,728,720
• 最終ジャッジ日時: 2024-02-25 16:24:33
• 合計ジャッジ時間: 52,486 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

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

コンパイルメッセージ

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

warning: 1 warning emitted

ソースコード

use std::io;
use std::env;

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() {
    env::set_var("RUST_BACKTRACE", "1");

    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 best_score = 0;
    let mut sol = vec![];
    // let mut rng = PcgXshRr::new(123, 456);
    let timer = Timer::new(0.98);
    while ! timer.is_timeout() {
        let f_now = a[0].0;
        let b_now = a[0].1;
        let mut current_best = best_score;
        let mut next_action = (1, 2);
        for i in 1..n {
            let f_new = ((f_now + a[i].0) as f64 / 2f64).ceil() as u64;
            let b_new = ((b_now + a[i].1) as f64 / 2f64).ceil() as u64;
            let new_score = calc_score((f_new, b_new));
            if new_score > current_best {
                current_best = new_score;
                next_action = (1, i + 1);
            }
        }

        if current_best > best_score {
            best_score = current_best;
            a[0].0 = ((f_now + a[next_action.0 - 1].0) as f64 / 2f64).ceil() as u64;
            a[0].1 = ((b_now + a[next_action.1 - 1].1) as f64 / 2f64).ceil() as u64;
            sol.push(next_action);
        }
    }
    eprintln!("inisol score = {}", best_score);

    
    println!("{}", sol.len());
    for (r1, r2) in sol {
        let r2 = if r1 == r2 { r2 + 1 } else { r2 };
        println!("{} {}", r1, r2);
    }
    eprintln!("best score = {}", best_score);
    std::process::exit(0);
}

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