結果

問題 No.5020 Averaging
ユーザー tmzntmzn
提出日時 2024-02-25 16:23:40
言語 Rust
(1.77.0)
結果
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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 981 ms
6,548 KB
testcase_01 AC 981 ms
6,548 KB
testcase_02 AC 981 ms
6,548 KB
testcase_03 AC 982 ms
6,548 KB
testcase_04 AC 981 ms
6,548 KB
testcase_05 AC 982 ms
6,548 KB
testcase_06 AC 981 ms
6,548 KB
testcase_07 AC 981 ms
6,548 KB
testcase_08 AC 981 ms
6,548 KB
testcase_09 AC 981 ms
6,548 KB
testcase_10 AC 981 ms
6,548 KB
testcase_11 AC 981 ms
6,548 KB
testcase_12 AC 981 ms
6,548 KB
testcase_13 AC 980 ms
6,548 KB
testcase_14 AC 981 ms
6,548 KB
testcase_15 AC 981 ms
6,548 KB
testcase_16 AC 981 ms
6,548 KB
testcase_17 AC 981 ms
6,548 KB
testcase_18 AC 981 ms
6,548 KB
testcase_19 AC 981 ms
6,548 KB
testcase_20 AC 980 ms
6,548 KB
testcase_21 AC 981 ms
6,548 KB
testcase_22 AC 981 ms
6,548 KB
testcase_23 AC 980 ms
6,548 KB
testcase_24 AC 981 ms
6,548 KB
testcase_25 AC 981 ms
6,548 KB
testcase_26 AC 981 ms
6,548 KB
testcase_27 AC 981 ms
6,548 KB
testcase_28 AC 981 ms
6,548 KB
testcase_29 AC 982 ms
6,548 KB
testcase_30 AC 981 ms
6,548 KB
testcase_31 AC 981 ms
6,548 KB
testcase_32 AC 981 ms
6,548 KB
testcase_33 AC 981 ms
6,548 KB
testcase_34 AC 980 ms
6,548 KB
testcase_35 AC 981 ms
6,548 KB
testcase_36 AC 981 ms
6,548 KB
testcase_37 AC 982 ms
6,548 KB
testcase_38 AC 981 ms
6,548 KB
testcase_39 AC 981 ms
6,548 KB
testcase_40 AC 981 ms
6,548 KB
testcase_41 AC 982 ms
6,548 KB
testcase_42 AC 981 ms
6,548 KB
testcase_43 AC 981 ms
6,548 KB
testcase_44 AC 981 ms
6,548 KB
testcase_45 AC 982 ms
6,548 KB
testcase_46 AC 981 ms
6,548 KB
testcase_47 AC 981 ms
6,548 KB
testcase_48 AC 981 ms
6,548 KB
testcase_49 AC 981 ms
6,548 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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

ソースコード

diff # 

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
}
0