結果

問題 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

ソースコード

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