結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 16:44:57 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 952 ms / 1,000 ms |
コード長 | 7,378 bytes |
コンパイル時間 | 1,132 ms |
コンパイル使用メモリ | 194,900 KB |
実行使用メモリ | 6,676 KB |
スコア | 47,637,392 |
最終ジャッジ日時 | 2024-02-25 16:48:02 |
合計ジャッジ時間 | 51,649 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
コンパイルメッセージ
warning: variable does not need to be mutable --> Main.rs:7:13 | 7 | let mut s = { | ----^ | | | help: remove this `mut` ... 78 | / input! { 79 | | n: usize, 80 | | c: [(i64, i64); n], 81 | | } | |_________- in this macro invocation | = note: `#[warn(unused_mut)]` on by default = note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info) warning: 1 warning emitted
ソースコード
macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let mut s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}pub trait ChangeMinMax {fn change_min(&mut self, v: Self) -> bool;fn change_max(&mut self, v: Self) -> bool;}impl<T: PartialOrd> ChangeMinMax for T {fn change_min(&mut self, v: T) -> bool {*self > v && {*self = v;true}}fn change_max(&mut self, v: T) -> bool {*self < v && {*self = v;true}}}struct Input {n: usize,cards: Vec<(i64, i64)>,}impl Input {fn read_input() -> Self {input! {n: usize,c: [(i64, i64); n],}let mut cards = vec![];for (a, b) in c {let a = a - 500_000_000_000_000_000;let b = b - 500_000_000_000_000_000;cards.push((a, b));}Input { n, cards }}}#[derive(Debug, Clone)]struct State {operations: Vec<(usize, usize)>,}impl State {fn new() -> Self {State { operations: vec![] }}fn calc_score(&self, input: &Input) -> i64 {let mut cards = input.cards.clone();for &(a, b) in &self.operations {let x = (cards[a].0 + cards[b].0) / 2;let y = (cards[a].1 + cards[b].1) / 2;cards[a] = (x, y);cards[b] = (x, y);}let v1 = cards[0].0.abs();let v2 = cards[0].1.abs();let max = v1.max(v2);if max == 0 {2000050 - self.operations.len() as i64} else {(2e6 - 1e5 * (max as f64 + 1.0).log10()).floor() as i64}}}fn main() {let input = Input::read_input();let initial_solution = State::new();let solution = annealing(&input, initial_solution, 0.95);println!("{}", solution.operations.len());for (a, b) in solution.operations {println!("{} {}", a + 1, b + 1);}}fn annealing(input: &Input, initial_solution: State, duration: f64) -> State {let mut solution = initial_solution;let mut best_solution = solution.clone();let mut current_score = solution.calc_score(input);let mut best_score = current_score;let init_score = current_score;let mut all_iter = 0;let mut valid_iter = 0;let mut accepted_count = 0;let mut update_count = 0;let mut rng = Xorshift::new();let duration_inv = 1.0 / duration;let since = std::time::Instant::now();let temp0 = 1e5;let temp1 = 3e2;let mut inv_temp = 1.0 / temp0;loop {all_iter += 1;if (all_iter & ((1 << 4) - 1)) == 0 {let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);inv_temp = 1.0 / temp;if time >= 1.0 {break;}}// 変形let neigh_type = rng.rand(4);let mut new_state = solution.clone();if neigh_type == 0 {if new_state.operations.len() >= 50 {continue;}let (i, j) = loop {let i = (rng.rand(input.n as u64 * 3) as usize).saturating_sub(input.n * 2);let j = rng.rand(input.n as u64) as usize;if i != j {break (i, j);}};let pos = rng.rand(solution.operations.len() as u64 + 1) as usize;new_state.operations.insert(pos, (i, j));} else if neigh_type == 1 {if new_state.operations.is_empty() {continue;}let pos = rng.rand(solution.operations.len() as u64) as usize;new_state.operations.remove(pos);} else {if new_state.operations.len() < 2 {continue;}let (i, j) = loop {let i = rng.rand(new_state.operations.len() as u64) as usize;let j = rng.rand(new_state.operations.len() as u64) as usize;if i != j {break (i, j);}};new_state.operations.swap(i, j);}// スコア計算let new_score = new_state.calc_score(input);let score_diff = new_score - current_score;if score_diff >= 0 || rng.randf() < f64::exp(score_diff as f64 * inv_temp) {// 解の更新solution = new_state;current_score = new_score;accepted_count += 1;if best_score.change_max(current_score) {best_solution = solution.clone();update_count += 1;}}valid_iter += 1;}eprintln!("===== annealing =====");eprintln!("init score : {}", init_score);eprintln!("score : {}", best_score);eprintln!("all iter : {}", all_iter);eprintln!("valid iter : {}", valid_iter);eprintln!("accepted : {}", accepted_count);eprintln!("updated : {}", update_count);eprintln!("");best_solution}// https://qiita.com/hatoo@github/items/652b81e8e83b0680bc0a#[derive(Debug)]#[allow(dead_code)]pub struct Xorshift {seed: u64,}impl Xorshift {#[allow(dead_code)]pub fn new() -> Xorshift {Xorshift {seed: 0xf0fb588ca2196dac,}}#[allow(dead_code)]pub fn with_seed(seed: u64) -> Xorshift {Xorshift { seed: seed }}#[inline]#[allow(dead_code)]pub fn next(&mut self) -> u64 {self.seed = self.seed ^ (self.seed << 13);self.seed = self.seed ^ (self.seed >> 7);self.seed = self.seed ^ (self.seed << 17);self.seed}#[inline]#[allow(dead_code)]pub fn rand(&mut self, m: u64) -> u64 {self.next() % m}#[inline]#[allow(dead_code)]// 0.0 ~ 1.0pub fn randf(&mut self) -> f64 {use std::mem;const UPPER_MASK: u64 = 0x3FF0000000000000;const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;let tmp = UPPER_MASK | (self.next() & LOWER_MASK);let result: f64 = unsafe { mem::transmute(tmp) };result - 1.0}}