結果

問題 No.5007 Steiner Space Travel
ユーザー r3yoheir3yohei
提出日時 2023-04-26 22:59:12
言語 Rust
(1.77.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 6,663 bytes
コンパイル時間 1,366 ms
コンパイル使用メモリ 154,820 KB
実行使用メモリ 4,376 KB
スコア 1,221,702
最終ジャッジ日時 2023-04-26 22:59:17
合計ジャッジ時間 3,402 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,368 KB
testcase_01 AC 1 ms
4,372 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 1 ms
4,372 KB
testcase_04 AC 1 ms
4,368 KB
testcase_05 AC 1 ms
4,372 KB
testcase_06 AC 2 ms
4,368 KB
testcase_07 AC 2 ms
4,372 KB
testcase_08 AC 1 ms
4,372 KB
testcase_09 AC 1 ms
4,368 KB
testcase_10 AC 1 ms
4,368 KB
testcase_11 AC 1 ms
4,368 KB
testcase_12 AC 2 ms
4,368 KB
testcase_13 AC 1 ms
4,372 KB
testcase_14 AC 1 ms
4,372 KB
testcase_15 AC 1 ms
4,368 KB
testcase_16 AC 1 ms
4,372 KB
testcase_17 AC 1 ms
4,368 KB
testcase_18 AC 1 ms
4,372 KB
testcase_19 AC 1 ms
4,368 KB
testcase_20 AC 1 ms
4,368 KB
testcase_21 AC 1 ms
4,372 KB
testcase_22 AC 2 ms
4,368 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,372 KB
testcase_25 AC 2 ms
4,372 KB
testcase_26 AC 2 ms
4,368 KB
testcase_27 AC 1 ms
4,368 KB
testcase_28 AC 1 ms
4,372 KB
testcase_29 AC 1 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused)]

use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
use crate::input::{*, marker::*};

// コピペで使える proconio もどき
// cunitacさんからお借りしています
// https://gist.github.com/cunitac/b00be62bf68c9fb6055d22eb77c17e14
pub mod input {
    use std::{
        cell::RefCell,
        fmt::Debug,
        io::{stdin, BufRead, BufReader, Stdin},
        str::{FromStr, SplitWhitespace},
    };

    thread_local!(
        pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {
            stdin: BufReader::new(stdin()),
            tokens: "".split_whitespace(),
        });
    );

    pub struct Source {
        stdin: BufReader<Stdin>,
        tokens: SplitWhitespace<'static>,
    }
    impl Source {
        pub fn next_token(&mut self) -> Option<&str> {
            self.tokens.next().or_else(|| {
                let mut input = String::new();
                self.stdin.read_line(&mut input).unwrap();
                self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();
                self.tokens.next()
            })
        }
    }
    #[macro_export]
    macro_rules! read_value {
        (from $s:expr, [$t:tt; $n:expr]) => {
            (0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()
        };
        (from $s:expr, [$t:tt]) => {
            let n = $crate::read_value!(from $s, usize);
            $crate::read_value!(from $s, [$t; n])
        };
        (from $s:expr, $t:ty) => {
            <$t as $crate::input::Readable>::read(&mut $s)
        };
        (from $s:expr, $($t:tt),* $(,)?) => {
            ($($crate::read_value!(from $s, $t)),*)
        };
        ($($r:tt)*) => {
            $crate::input::STDIN_SOURCE.with(|s| {
                let mut s = s.borrow_mut();
                $crate::read_value!(from s, $($r)*)
            })
        }
    }
    #[macro_export]
    macro_rules! input {
        () => {
        };
        ($x:tt: $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (mut $x:tt: $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        (from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        ($($r:tt)*) => {
            $crate::input!($($r)*,);
        };
    }
    pub trait Readable {
        type Output;
        fn read(source: &mut Source) -> Self::Output;
    }
    impl<T: FromStr<Err = E>, E: Debug> Readable for T {
        type Output = T;
        fn read(source: &mut Source) -> T {
            source.next_token().unwrap().parse().unwrap()
        }
    }
    pub mod marker {
        macro_rules! impl_readable {
            ($e:ident, $t:ty, $u:ty, $f:expr) => {
                pub enum $e {}
                impl $crate::input::Readable for $e {
                    type Output = $t;
                    fn read(mut source: &mut $crate::input::Source) -> $t {
                        $f($crate::read_value!(from source, $u))
                    }
                }
            };
        }
        impl_readable!(Usize1, usize, usize, |x| x - 1);
        impl_readable!(Isize1, isize, isize, |x| x - 1);
        impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());
        impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());
    }
}

const N: usize = 100;
const M: usize = 8;
const ALPHA: i64 = 5;
const TL: f64 = 0.97;

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.5
        }
        #[cfg(not(feature = "local"))]
        {
            (ms - STIME)
        }
    }
}

// 距離の二乗を返す
pub fn squared_distance(x1: i64, y1: i64, x2: i64, y2: i64) -> i64 {
    (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
}

#[derive(Clone)]
struct Input {
    pos: Vec<(i64, i64)>,
}
impl Input {
    pub fn new() -> Self {
        input! {
            _n: usize,
            _m: usize,
        }
        let mut pos = vec![];
        for _ in 0..N {
            input! {
                ai: i64,
                bi: i64,
            }
            pos.push((ai, bi));
        }
        Self { pos }
    }
}

#[derive(Clone)]
struct State {
    turn: i64,
    is_done: bool,
    game_score: i64,
    evaluated_score: i64,
    station: Vec<(i64, i64)>, // i番目のステーションの場所
    route: Vec<(usize, usize)>, // 道順 (惑星orステーション，番号)
}
impl State {
    pub fn new() -> Self {
        let mut station = vec![
            (300, 300), (300, 600), (300, 900),
            (600, 300), (600, 900),
            (900, 300), (900, 600), (900, 900)
        ];
        let mut route = vec![];
        for i in 0..N {
            route.push((1, i));
        }
        route.push((1, 0));
        Self {
            turn: 0,
            is_done: false,
            game_score: 0,
            evaluated_score: 0,
            station,
            route,
        }
    }
    pub fn print(&self) {
        for i in 0..M {
            let (ci, di) = self.station[i];
            println!("{} {}", ci, di);
        }
        let v = self.route.len();
        println!("{}", v);
        for i in 0..v {
            let (ti, ri) = self.route[i];
            println!("{} {}", ti, ri + 1);
        }
    }
}

fn main() {
    // 2-optに見えるが，再訪ありなので単純には適応できない
    // ただ，宇宙ステーションに再訪してもいいが，惑星は再訪しないほうがよい
    // 近傍: 
    // - 2-opt
    // - 少なくとも一方が宇宙ステーションであるパスの追加
    // - いずれかの宇宙ステーションの座標をずらす (あるいは，これはあらかじめk-meansで求めておく)
    get_time();
    let input = Input::new();
    let mut state = State::new();

    state.print();
    eprintln!("score: {}", state.game_score);
    eprintln!("time: {}", get_time());
}
0