結果

問題 No.5020 Averaging
ユーザー EvbCFfp1XBEvbCFfp1XB
提出日時 2024-02-25 16:27:40
言語 Rust
(1.77.0 + proconio)
結果
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

ソースコード

diff # 

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