結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:07:39 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 11,006 bytes |
コンパイル時間 | 1,289 ms |
実行使用メモリ | 9,228 KB |
スコア | 0 |
最終ジャッジ日時 | 2022-10-14 23:08:09 |
合計ジャッジ時間 | 8,432 ms |
ジャッジサーバーID (参考情報) |
judge8 / judge9 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 49 |
コンパイルメッセージ
warning: variable `inv_temp` is assigned to, but never used --> Main.rs:304:13 | 304 | let mut inv_temp = 1.0 / temp0; | ^^^^^^^^ | = note: `#[warn(unused_variables)]` on by default = note: consider using `_inv_temp` instead warning: value assigned to `inv_temp` is never read --> Main.rs:311:13 | 311 | inv_temp = 1.0 / temp; | ^^^^^^^^ | = note: `#[warn(unused_assignments)]` on by default = help: maybe it is overwritten before being read? warning: 2 warnings emitted
ソースコード
macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}#[allow(unused_macros)]macro_rules! chmin {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_min = min!($($cmps),+);if $base > cmp_min {$base = cmp_min;true} else {false}}};}#[allow(unused_macros)]macro_rules! chmax {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_max = max!($($cmps),+);if $base < cmp_max {$base = cmp_max;true} else {false}}};}#[allow(unused_macros)]macro_rules! min {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{std::cmp::min($a, $b)}};($a:expr, $($rest:expr),+ $(,)*) => {{std::cmp::min($a, min!($($rest),+))}};}#[allow(unused_macros)]macro_rules! max {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{std::cmp::max($a, $b)}};($a:expr, $($rest:expr),+ $(,)*) => {{std::cmp::max($a, max!($($rest),+))}};}#[allow(unused_macros)]macro_rules! mat {($e:expr; $d:expr) => { vec![$e; $d] };($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };}#[allow(unused_macros)]macro_rules! skip_none {($res:expr) => {if let Some(v) = $res {v} else {continue;}};}#[derive(Debug, Clone)]struct Input {n: usize,_k: usize,oppose_times: Vec<i64>,coop_times: Vec<i64>,}impl Input {fn read_input() -> Self {input! {n: usize,k: usize,oppose_times: [i64; k],coop_times: [i64; k]}Self {n,_k: k,oppose_times,coop_times,}}}#[derive(Debug, Clone)]struct State {pendulums: Vec<Pendulum>,}impl State {fn calc_score_all(&self, input: &Input) -> i64 {let mut oppose_x = Vec::with_capacity(self.pendulums.len());let mut coop_x = Vec::with_capacity(self.pendulums.len());for p in self.pendulums.iter() {let op = p.get_all_x(&input.oppose_times);let co = p.get_all_x(&input.coop_times);oppose_x.push(op);coop_x.push(co);}let mut oppose_sum = 0.0;let mut coop_sum = 0.0;for i in 0..oppose_x.len() {let xi = &oppose_x[i];let pi = &self.pendulums[i];for j in (i + 1)..oppose_x.len() {let xj = &oppose_x[j];let pj = &self.pendulums[j];for (x, y) in xi.iter().zip(xj) {oppose_sum += (x - y).abs() as f64 / (pi.init + pj.init) as f64;}}}let mut max = vec![std::i64::MIN; coop_x.len()];let mut min = vec![std::i64::MAX; coop_x.len()];for x in coop_x.iter() {for (i, &x) in x.iter().enumerate() {chmax!(max[i], x);chmin!(min[i], x);}}for i in 0..coop_x.len() {coop_sum += ((max[i] - min[i]) as f64 * 0.05 + 1.0).sqrt();}let oppose_score = oppose_sum * 2e7 / (input.n * (input.n - 1)) as f64;let coop_score = 1e7 / coop_sum;(oppose_score * coop_score).round() as i64}}#[derive(Debug, Clone, Copy)]struct Pendulum {init: i64,min: i64,damper: i64,}impl Pendulum {fn new(init: i64, min: i64, damper: i64) -> Self {Self { init, min, damper }}fn get_x(&self, time: i64) -> i64 {// 振幅がmin以下になる時間let min_round = (self.init - self.min) / self.damper;let init_period = self.get_period(0);let last_period = self.get_period(min_round);let min_t = min_round * (init_period + last_period) / 2;let round = if time >= min_t {min_round} else {binary_search(&|round| {let last_period = self.get_period(round);let t = min_round * (init_period + last_period) / 2;t <= time},0,(time + init_period - 1) / init_period + 1,)};let round_period = self.get_period(round);let mut t = round * (init_period + round_period) / 2;let mut amp = self.get_amp(round);let mut dir = 1;loop {let remain = time - t;if remain <= 2 * amp {if remain <= amp {return dir * remain;} else {return dir * (2 * amp - remain);}}t += 2 * amp;amp -= self.damper;amp = amp.max(self.min);dir = -dir;}}fn get_all_x(&self, times: &[i64]) -> Vec<i64> {let mut x = Vec::with_capacity(times.len());for &t in times {x.push(self.get_x(t));}x}fn get_amp(&self, round: i64) -> i64 {(self.init - self.damper * round * 2).max(self.min)}fn get_period(&self, round: i64) -> i64 {self.get_amp(round) * 4 - 4}}fn main() {let input = Input::read_input();let state = get_init_state(&input);let state = annealing(&input, state, 1.9);eprintln!("{}", state.calc_score_all(&input));}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_all(input);let mut best_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(42);let duration_inv = 1.0 / duration;let since = std::time::Instant::now();let mut time = 0.0;let temp0 = 1e5;let temp1 = 1e3;let mut inv_temp = 1.0 / temp0;while time < 1.0 {all_iter += 1;if (all_iter & ((1 << 4) - 1)) == 0 {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;}// 変形let index = rng.rand(input.n as u64) as usize;let sign = rng.rand(2) as i64 * 2 - 1;let change_type = rng.rand(3);let mut new_state = solution.clone();if change_type == 1 {let new_init = new_state.pendulums[index].init + sign;if new_init <= 0 || new_init > 1_000_000_000 {continue;}new_state.pendulums[index].init = new_init;} else if change_type == 2 {let new_min = new_state.pendulums[index].min + sign;if new_min <= 0 || new_min > new_state.pendulums[index].init {continue;}new_state.pendulums[index].min = new_min;} else {let damper = new_state.pendulums[index].damper + sign;if damper <= 0|| damper > new_state.pendulums[index].init - new_state.pendulums[index].min{continue;}new_state.pendulums[index].damper = damper;};// スコア計算let new_score = new_state.calc_score_all(input);let score_diff = new_score - current_score;if score_diff >= 0 {//|| rng.randf() < f64::exp(score_diff as f64 * inv_temp) {// 解の更新current_score = new_score;solution = new_state;accepted_count += 1;if chmax!(best_score, current_score) {best_solution = solution.clone();update_count += 1;}}valid_iter += 1;}eprintln!("===== annealing =====");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}fn get_init_state(input: &Input) -> State {let mut pendulums = vec![];for _ in 0..input.n {pendulums.push(Pendulum::new(1, 1, 1));}State { pendulums }}fn binary_search<F: Fn(i64) -> bool>(f: &F, mut ok: i64, mut ng: i64) -> i64 {while (ok - ng).abs() > 1 {let mid = (ok + ng) / 2;if f(mid) {ok = mid;} else {ng = mid;}}ok}#[derive(Debug)]#[allow(dead_code)]pub struct Xorshift {seed: u64,}#[allow(dead_code)]impl Xorshift {pub fn new(seed: u64) -> Xorshift {Xorshift { seed }}#[inline]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]pub fn rand(&mut self, m: u64) -> u64 {self.next() % m}#[inline]// 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}}