結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー terry_u16
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

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