結果

問題 No.1413 Dynamic Sushi
ユーザー StrorkisStrorkis
提出日時 2021-03-01 12:59:23
言語 Rust
(1.72.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,255 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 102,384 KB
最終ジャッジ日時 2023-07-26 13:38:12
合計ジャッジ時間 1,705 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error: format argument must be a string literal
 --> Main.rs:8:34
  |
8 |                 Err(e) => panic!(e), 
  |                                  ^
  |
help: you might be missing a string literal to format with
  |
8 |                 Err(e) => panic!("{}", e), 
  |                                  +++++

error: aborting due to previous error

ソースコード

diff #

mod io {
    pub fn scan<R: std::io::BufRead>(r: &mut R) -> Vec<u8> {
        let mut res = Vec::new();
        loop {
            let buf = match r.fill_buf() {
                Ok(buf) => buf,
                Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
                Err(e) => panic!(e), 
            };
            let (done, used, buf) = {
                match buf.iter().position(u8::is_ascii_whitespace) {
                    Some(i) => (i > 0 || res.len() > 0, i + 1, &buf[..i]),
                    None => (buf.is_empty(), buf.len(), buf),
                }
            };
            res.extend_from_slice(buf);
            r.consume(used);
            if done { return res; }
        }
    }
}

use std::f64::consts::PI;

const FRAC_PI_180: f64 = PI / 180.0;
const INF: f64 = 1e9;
const EPS: f64 = 1e-9;

struct Sushi {
    x: f64, y: f64, r: f64, v: f64, a: f64,
}

impl Sushi {
    fn pos(&self, t: f64) -> (f64, f64) {
        let x = self.x + self.r * ((self.v * t + self.a) * FRAC_PI_180).cos();
        let y = self.y + self.r * ((self.v * t + self.a) * FRAC_PI_180).sin();
        (x, y)
    }

    fn time(&self, w: f64, t0: f64, (x0, y0): (f64, f64)) -> f64 {
        let mut left = t0;
        let mut right = t0 + ((self.x - x0).hypot(self.y - y0) + self.r) / w + EPS;
        while (left - right).abs() > EPS {
            let t = (left + right) * 0.5;
            let (x, y) = self.pos(t);
            if (t - t0) * w <= (x - x0).hypot(y - y0) {
                left = t;
            } else {
                right = t;
            }
        }
        left
    }
}

#[allow(unused_macros)]
fn run<R: std::io::BufRead, W: std::io::Write>(reader: &mut R, writer: &mut W) {
    macro_rules! scan {
        ([$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($t)).collect::<Vec<_>>());
        (($($t:tt),*)) => (($(scan!($t)),*));
        ([u8]) => (io::scan(reader));
        (String) => (unsafe { String::from_utf8_unchecked(scan!([u8])) });
        ($t:ty) => (scan!(String).parse::<$t>().unwrap());
    }
    macro_rules! println {
        ($($arg:tt)*) => (writeln!(writer, $($arg)*).ok());
    }

    let (n, w) = scan!((usize, f64));

    let sushi = {
        let mut sushi = Vec::with_capacity(n);
        for _ in 0..n {
            let (x, y, r, v, a) = scan!((f64, f64, f64, f64, f64));
            sushi.push(Sushi { x, y, r, v, a });
        }
        sushi
    };

    let mut dp = vec![vec![INF; n]; 1 << n];
    for i in 0..n {
        dp[1 << i][i] = sushi[i].time(w, 0.0, (0.0, 0.0));
    }
    for bit in 1..(1 << n) {
        for i in 0..n {
            let t = dp[bit][i];
            if bit >> i & 1 == 0 { continue; }
            let pos = sushi[i].pos(t);
            for j in 0..n {
                if bit >> j & 1 == 1 { continue; }
                let nt = &mut dp[bit | 1 << j][j];
                *nt = (*nt).min(sushi[j].time(w, t, pos));
            }
        }
    }
    println!("{}", dp.last().unwrap().iter().fold(INF, |acc, t| acc.min(*t)));
}

fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let mut reader = std::io::BufReader::new(stdin.lock());
    let mut writer = std::io::BufWriter::new(stdout.lock());
    run(&mut reader, &mut writer);
}
0