結果
| 問題 | No.5020 Averaging |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2024-02-25 16:27:40 |
| 言語 | Rust (1.83.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 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
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
ソースコード
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 Annealinglet 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, temperatureif (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)}