#955638 (Rust) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	EvbCFfp1XB
提出日時	2024-02-25 16:27:40
言語	Rust (1.77.0)
結果	AC
実行時間	952 ms / 1,000 ms
コード長	5,504 bytes
コンパイル時間	1,827 ms
コンパイル使用メモリ	189,592 KB
実行使用メモリ	6,548 KB
スコア	42,878,332
最終ジャッジ日時	2024-02-25 16:29:16
合計ジャッジ時間	51,350 ms
ジャッジサーバーID （参考情報）	judge15 / judge10
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

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

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused import: `Duration`
 --> Main.rs:1:29
  |
1 | use std::time::{SystemTime, Duration};
  |                             ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: method `nextInt` should have a snake case name
  --> Main.rs:16:16
   |
16 |         pub fn nextInt(&mut self) -> u32 {
   |                ^^^^^^^ help: convert the identifier to snake case: `next_int`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: method `nextDouble` should have a snake case name
  --> Main.rs:28:16
   |
28 |         pub fn nextDouble(&mut self) -> f64 {
   |                ^^^^^^^^^^ help: convert the identifier to snake case: `next_double`

warning: method `nextIntMod` should have a snake case name
  --> Main.rs:32:16
   |
32 |         pub fn nextIntMod(&mut self, n: u32) -> u32 {
   |                ^^^^^^^^^^ help: convert the identifier to snake case: `next_int_mod`

warning: 4 warnings emitted

ソースコード

raw source code

use std::time::{SystemTime, Duration};

pub mod random {

    pub struct PcgXshRr {
        state: u64,
    }

    impl PcgXshRr {
        pub fn new(state: u64) -> Self {
            PcgXshRr {
                state,
            }
        }

        pub fn nextInt(&mut self) -> u32 {
            let oldstate = self.state;
            self.state = oldstate * 6364136223846793005u64 + 521u64;
            let xorshift : u32 = (((oldstate >> 18 ) ^ oldstate) >> 27) as u32 ;
            let rotation : u32 = (oldstate >> 59 ) as u32;
            return (xorshift >> rotation) | (xorshift << ((-1 * rotation as i32) & 31));
        }

        pub fn gen(&mut self) -> u32 {
            return self.nextInt();
        }

        pub fn nextDouble(&mut self) -> f64 {
            return (self.nextInt() as f64) * 0.00000000023283064365386963; // 1 / (1 << 32)
        }

        pub fn nextIntMod(&mut self, n: u32) -> u32 {
//            return (n as f64 * self.nextDouble()) as u32;
            return self.nextInt() % n;
        }
    }
}


fn main() {
    let start_time = get_time();
    let mut rng = {
        let t = SystemTime::now()
            .duration_since(SystemTime::UNIX_EPOCH)
            .unwrap();
        let seed = t.subsec_nanos() as u64 ^ 114514;
        random::PcgXshRr::new(seed)
    };

    let n: usize = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };

    let mut a = vec![!0; n];
    let mut b = vec![!0; n];
    for i in 0..n {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut nums = line.trim().split_whitespace().map(|x| x.parse::<i64>().unwrap());
        let e = nums.next().unwrap();
        let f = nums.next().unwrap();
        a[i] = e;
        b[i] = f;
    }

    let mut solution = vec![];
    for _ in 0..50 {
        let i = 0;
        let mut j = rng.gen() as usize % (n - 1);
        if j >= i {
            j += 1;
        }
        solution.push((i, j));
    }

    let mut score = calculate_score(&solution, &a, &b);

    // Simulated Annealing
    let start_temperature = 1e4;
    let end_temperature = 1e-9;
    let mut temperature = start_temperature;

    let end_time = 0.95;

    let mut iterations = 0;
    let mut acs = 0;
    loop {
        iterations += 1;
        // Update time, temperature
        if (iterations & ((1 << 10) - 1)) == 0 {
            let time = get_time();
            temperature = start_temperature + (end_temperature - start_temperature) * (time - start_time) / (end_time - start_time);
            if time > end_time {
                eprintln!("iterations:{:7}, ac:{:.02}%, score:{:7}", iterations, acs as f64 * 100.0 / iterations as f64, score);
                break;
            }
        }

        let random = rng.gen() as usize % 2;
        if random < 1 {
            let index = rng.gen() as usize % solution.len();
            let (current_i, current_j) = solution[index];
            let new_i = rng.gen() as usize % n;
            let mut new_j = rng.gen() as usize % (n - 1);
            if new_j >= new_i {
                new_j += 1;
            }
    
            solution[index] = (new_i, new_j);
    
            let before = score;
            let after  = calculate_score(&solution, &a, &b);
            let delta_score = after - before;
            if delta_score <= 0 || rng.nextDouble() < (-delta_score as f64 / temperature).exp() {
                acs += 1;
                score += delta_score;
            } else {
                solution[index] = (current_i, current_j);
            }
        } else if random < 2 {
            let index1 = rng.gen() as usize % solution.len();
            let mut  index2 = rng.gen() as usize % (solution.len() - 1);
            if index2 >= index1 {
                index2 += 1;
            }

            {
                let swap = solution[index1];
                solution[index1] = solution[index2];
                solution[index2] = swap;
            }


            let before = score;
            let after  = calculate_score(&solution, &a, &b);
            let delta_score = after - before;
            if delta_score <= 0 || rng.nextDouble() < (-delta_score as f64 / temperature).exp() {
                acs += 1;
                score += delta_score;
            } else {
                let swap = solution[index1];
                solution[index1] = solution[index2];
                solution[index2] = swap;
            }
        }
    }

    println!("{}", solution.len());
    for i in 0..solution.len() {
        println!("{} {}", 1 + solution[i].0, 1 + solution[i].1);
    }

}

fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = SystemTime::now()
        .duration_since(SystemTime::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

fn calculate_score(solution: &Vec<(usize, usize)>, a0: &Vec<i64>, b0: &Vec<i64>) -> i64 {
    let mut a = a0.clone();
    let mut b = b0.clone();
    for k in 0..solution.len() {
        let (i, j) = solution[k];
        let new_a = (a[i] + a[j]) >> 1;
        let new_b = (b[i] + b[j]) >> 1;
        a[i] = new_a;
        b[i] = new_b;
        a[j] = new_a;
        b[j] = new_b;
    }
    let v1 = (a[0] - 5e17 as i64).abs();
    let v2 = (b[0] - 5e17 as i64).abs();
    v1.max(v2)
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード