結果

問題 No.5020 Averaging
コンテスト
ユーザー tmzn
提出日時 2024-02-25 14:02:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,495 bytes
コンパイル時間 687 ms
コンパイル使用メモリ 191,716 KB
実行使用メモリ 6,676 KB
スコア 14,792,731
最終ジャッジ日時 2024-02-25 14:02:49
合計ジャッジ時間 2,446 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: struct `Timer` is never constructed
 --> Main.rs:7:8
  |
7 | struct Timer {
  |        ^^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: associated items `new`, `reset`, `elapsed`, and `is_timeout` are never used
  --> Main.rs:13:8
   |
12 | impl Timer {
   | ---------- associated items in this implementation
13 |     fn new(end: f64) -> Timer {
   |        ^^^
...
20 |     fn reset(&mut self) {
   |        ^^^^^
...
24 |     fn elapsed(&self) -> f64 {
   |        ^^^^^^^
...
35 |     fn is_timeout(&self) -> bool {
   |        ^^^^^^^^^^

warning: 2 warnings emitted

ソースコード

diff # 

use std::io;

use std::time::Instant;

const ANS: usize = 50_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));
    }
    eprintln!("score = {}", calc_score(&sol));

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

    // let mut timer = Timer::new(0.98);
    // while !timer.is_timeout() {

    // }
}

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 - 1000000f64 * (d1.max(d2) as f64 + 1f64).log10()).ceil() as usize
}
0