結果

問題 No.5020 Averaging
ユーザー brthyyjpbrthyyjp
提出日時 2024-02-25 16:32:13
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 852 ms / 1,000 ms
コード長 6,345 bytes
コンパイル時間 1,150 ms
コンパイル使用メモリ 189,360 KB
実行使用メモリ 6,676 KB
スコア 41,598,972
最終ジャッジ日時 2024-02-25 16:33:00
合計ジャッジ時間 45,937 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 851 ms
6,676 KB
testcase_01 AC 852 ms
6,676 KB
testcase_02 AC 851 ms
6,676 KB
testcase_03 AC 852 ms
6,676 KB
testcase_04 AC 852 ms
6,676 KB
testcase_05 AC 851 ms
6,676 KB
testcase_06 AC 851 ms
6,676 KB
testcase_07 AC 851 ms
6,676 KB
testcase_08 AC 850 ms
6,676 KB
testcase_09 AC 851 ms
6,676 KB
testcase_10 AC 851 ms
6,676 KB
testcase_11 AC 851 ms
6,676 KB
testcase_12 AC 850 ms
6,676 KB
testcase_13 AC 851 ms
6,676 KB
testcase_14 AC 851 ms
6,676 KB
testcase_15 AC 852 ms
6,676 KB
testcase_16 AC 851 ms
6,676 KB
testcase_17 AC 851 ms
6,676 KB
testcase_18 AC 851 ms
6,676 KB
testcase_19 AC 850 ms
6,676 KB
testcase_20 AC 851 ms
6,676 KB
testcase_21 AC 851 ms
6,676 KB
testcase_22 AC 851 ms
6,676 KB
testcase_23 AC 851 ms
6,676 KB
testcase_24 AC 851 ms
6,676 KB
testcase_25 AC 851 ms
6,676 KB
testcase_26 AC 851 ms
6,676 KB
testcase_27 AC 851 ms
6,676 KB
testcase_28 AC 850 ms
6,676 KB
testcase_29 AC 851 ms
6,676 KB
testcase_30 AC 850 ms
6,676 KB
testcase_31 AC 851 ms
6,676 KB
testcase_32 AC 851 ms
6,676 KB
testcase_33 AC 851 ms
6,676 KB
testcase_34 AC 851 ms
6,676 KB
testcase_35 AC 852 ms
6,676 KB
testcase_36 AC 851 ms
6,676 KB
testcase_37 AC 851 ms
6,676 KB
testcase_38 AC 851 ms
6,676 KB
testcase_39 AC 851 ms
6,676 KB
testcase_40 AC 851 ms
6,676 KB
testcase_41 AC 850 ms
6,676 KB
testcase_42 AC 851 ms
6,676 KB
testcase_43 AC 851 ms
6,676 KB
testcase_44 AC 851 ms
6,676 KB
testcase_45 AC 851 ms
6,676 KB
testcase_46 AC 851 ms
6,676 KB
testcase_47 AC 851 ms
6,676 KB
testcase_48 AC 851 ms
6,676 KB
testcase_49 AC 851 ms
6,676 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `iter` is assigned to, but never used
  --> Main.rs:62:13
   |
62 |     let mut iter = 0;
   |             ^^^^
   |
   = note: consider using `_iter` instead
   = note: `#[warn(unused_variables)]` on by default

warning: methods `gen_i32`, `gen_f64`, and `gen_bool` are never used
   --> Main.rs:178:23
    |
149 |     impl Xoshiro256 {
    |     --------------- methods in this implementation
...
178 |         pub(crate) fn gen_i32(&mut self, lower: i32, upper: i32) -> i32 {
    |                       ^^^^^^^
...
184 |         pub(crate) fn gen_f64(&mut self) -> f64 {
    |                       ^^^^^^^
...
192 |         pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
    |                       ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 2 warnings emitted

ソースコード

diff # 

use std::io;
use std::time::{Instant, Duration};
//use rand::{thread_rng, Rng};
//use rand::seq::SliceRandom;
use std::f64; 

use crate::rand::Xoshiro256;

fn move_element<T: Clone>(vec: &Vec<T>, i: usize, j: usize) -> Vec<T> {
    let mut result = vec.clone(); // 元のベクタを複製して新しいベクタを作成
    let element = result.remove(i); // `i`番目の要素を取り出す
    let insert_position = if j > i { j - 1 } else { j }; // 挿入位置を調整
    result.insert(insert_position, element); // 要素を挿入
    result
}

fn main() {
    let start_time = Instant::now();
    let seed = 42;
    //let mut rng = thread_rng();
    let mut rng = Xoshiro256::new(seed);

    let m = 50;
    let time_limit = Duration::from_secs_f64(0.85);
    let l: i64 = 5*10_i64.pow(17);

    let mut input_string = String::new();
    io::stdin().read_line(&mut input_string).expect("Failed to read line");
    let n: usize = input_string.trim().parse().expect("Please type a number!");

    let mut a = vec![0; n];
    let mut b = vec![0; n];
    for i in 0..n {
        let mut input = String::new();
        io::stdin().read_line(&mut input).expect("Failed to read line");
        let parts: Vec<i64> = input
            .split_whitespace()
            .map(|x| x.parse().expect("Not an integer!"))
            .collect();
        a[i] = parts[0];
        b[i] = parts[1];
    }

    let mut ans = Vec::new();
    for _ in 0..(m-1) {
        let u = rng.gen_usize(0, n);
        let mut v = rng.gen_usize(0, n);
        while v == u {
            v = rng.gen_usize(0, n);
        }
        //let picks = (0..n).collect::<Vec<usize>>();
        //let &u = picks.choose(&mut rng).unwrap();
        //let &v = picks.choose(&mut rng).unwrap();
        ans.push((u, v));
    }
    //let v = rng.gen_range(1..n);
    let v = rng.gen_usize(1, n);
    ans.push((0, v));

    let mut cost = calc_score(&a, &b, &ans, l);

    let mut iter = 0;
    while Instant::now().duration_since(start_time) < time_limit {
        iter += 1;
        //let neigh = rng.gen_range(0..2);
        let neigh = rng.gen_usize(0, 2);
        if neigh == 0 {
            //let i = rng.gen_range(0..m);
            let i = rng.gen_usize(0, m);
            let pre = ans[i];
            if i != m-1 {
                let u = rng.gen_usize(0, n);
                let mut v = rng.gen_usize(0, n);
                while v == u {
                    v = rng.gen_usize(0, n);
                }
                //let picks = (0..n).collect::<Vec<usize>>();
                //let &u = picks.choose(&mut rng).unwrap();
                //let &v = picks.choose(&mut rng).unwrap();
                ans[i] = (u, v);
            } else {
                //let v = rng.gen_range(1..n);
                let v = rng.gen_usize(1, n);
                ans[i] = (0, v);
            }
            let new_cost = calc_score(&a, &b, &ans, l);
            if new_cost > cost {
                ans[i] = pre;
            } else {
                cost = new_cost;
            }
        } else {
            let i = rng.gen_usize(0, m);
            let j = rng.gen_usize(0, m);
            //let i = rng.gen_range(0..m-1);
            //let j = rng.gen_range(0..m-1);
            let new_ans = move_element(&ans, i, j);
            //ans.swap(i, j);
            let new_cost = calc_score(&a, &b, &new_ans, l);
            if new_cost > cost {
                //ans.swap(i, j); // Swap back if not better
                continue;
            } else {
                cost = new_cost;
                ans = new_ans;
            }
        }
    }

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

    // Score printing to stderr in Rust is not straightforward as in Python
    // and typically not done in basic Rust programs.
    let score = if cost != 0 {
        (2000000.0 - 100000.0 * ((cost + 1) as f64).log10()) as i64
    } else {
        2000050 - ans.len() as i64
    };
    eprintln!("{}", score);
}

fn calc_score(a: &Vec<i64>, b: &Vec<i64>, ans: &Vec<(usize, usize)>, l: i64) -> i64 {
    let mut ac = a.clone();
    let mut bc = b.clone();
    for &(u, v) in ans {
        let x = (ac[u] + ac[v]) / 2;
        ac[u] = x;
        ac[v] = x;
        let y = (bc[u] + bc[v]) / 2;
        bc[u] = y;
        bc[v] = y;
    }
    let v1 = (l - ac[0]).abs();
    let v2 = (l - bc[0]).abs();
    std::cmp::max(v1, v2)
}

mod rand {
    pub(crate) struct Xoshiro256 {
        s0: u64,
        s1: u64,
        s2: u64,
        s3: u64,
    }

    impl Xoshiro256 {
        pub(crate) fn new(mut seed: u64) -> Self {
            let s0 = split_mix_64(&mut seed);
            let s1 = split_mix_64(&mut seed);
            let s2 = split_mix_64(&mut seed);
            let s3 = split_mix_64(&mut seed);
            Self { s0, s1, s2, s3 }
        }

        fn next(&mut self) -> u64 {
            let result = (self.s1 * 5).rotate_left(7) * 9;
            let t = self.s1 << 17;

            self.s2 ^= self.s0;
            self.s3 ^= self.s1;
            self.s1 ^= self.s2;
            self.s0 ^= self.s3;
            self.s2 ^= t;
            self.s3 = self.s3.rotate_left(45);

            result
        }

        pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u64) as usize + lower
        }

        pub(crate) fn gen_i32(&mut self, lower: i32, upper: i32) -> i32 {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u64) as i32 + lower
        }

        pub(crate) fn gen_f64(&mut self) -> f64 {
            const UPPER_MASK: u64 = 0x3ff0000000000000;
            const LOWER_MASK: u64 = 0xfffffffffffff;
            let result = UPPER_MASK | (self.next() & LOWER_MASK);
            let result: f64 = unsafe { std::mem::transmute(result) };
            result - 1.0
        }

        pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
            self.gen_f64() < prob
        }
    }

    fn split_mix_64(x: &mut u64) -> u64 {
        *x += 0x9e3779b97f4a7c15;
        let mut z = *x;
        z = (z ^ z >> 30) * 0xbf58476d1ce4e5b9;
        z = (z ^ z >> 27) * 0x94d049bb133111eb;
        return z ^ z >> 31;
    }
}
0