結果

問題 No.5016 Worst Mayor
ユーザー terry_u16terry_u16
提出日時 2023-04-29 14:13:04
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 12,819 bytes
コンパイル時間 4,074 ms
コンパイル使用メモリ 155,760 KB
実行使用メモリ 24,300 KB
スコア 12,653,525,229
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 14:13:17
合計ジャッジ時間 11,026 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
23,280 KB
testcase_01 AC 83 ms
23,232 KB
testcase_02 AC 83 ms
23,220 KB
testcase_03 AC 82 ms
23,232 KB
testcase_04 AC 83 ms
23,232 KB
testcase_05 AC 84 ms
23,448 KB
testcase_06 AC 82 ms
23,388 KB
testcase_07 AC 83 ms
23,700 KB
testcase_08 AC 81 ms
23,832 KB
testcase_09 AC 77 ms
23,868 KB
testcase_10 AC 83 ms
23,448 KB
testcase_11 AC 83 ms
23,640 KB
testcase_12 AC 84 ms
23,856 KB
testcase_13 AC 79 ms
23,196 KB
testcase_14 AC 82 ms
24,084 KB
testcase_15 AC 84 ms
23,352 KB
testcase_16 AC 83 ms
23,460 KB
testcase_17 AC 83 ms
23,412 KB
testcase_18 AC 82 ms
23,460 KB
testcase_19 AC 80 ms
23,232 KB
testcase_20 AC 84 ms
23,232 KB
testcase_21 AC 83 ms
23,616 KB
testcase_22 AC 84 ms
23,496 KB
testcase_23 AC 85 ms
23,460 KB
testcase_24 AC 84 ms
24,300 KB
testcase_25 AC 85 ms
23,460 KB
testcase_26 AC 85 ms
24,192 KB
testcase_27 AC 85 ms
23,196 KB
testcase_28 AC 85 ms
24,300 KB
testcase_29 AC 84 ms
23,880 KB
testcase_30 AC 84 ms
24,168 KB
testcase_31 AC 83 ms
24,228 KB
testcase_32 AC 83 ms
23,484 KB
testcase_33 AC 82 ms
24,180 KB
testcase_34 AC 83 ms
23,196 KB
testcase_35 AC 83 ms
23,268 KB
testcase_36 AC 84 ms
23,844 KB
testcase_37 AC 83 ms
23,268 KB
testcase_38 AC 82 ms
23,244 KB
testcase_39 AC 85 ms
23,868 KB
testcase_40 AC 84 ms
23,232 KB
testcase_41 AC 84 ms
23,712 KB
testcase_42 AC 82 ms
23,472 KB
testcase_43 AC 82 ms
24,156 KB
testcase_44 AC 84 ms
23,496 KB
testcase_45 AC 83 ms
23,232 KB
testcase_46 AC 82 ms
23,628 KB
testcase_47 AC 83 ms
23,628 KB
testcase_48 AC 83 ms
23,820 KB
testcase_49 AC 83 ms
23,472 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `crate::rand::Xoshiro256`
 --> Main.rs:8:5
  |
8 | use crate::rand::Xoshiro256;
  |     ^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `input`
   --> Main.rs:242:15
    |
242 | fn get_action(input: &Input, state: &State, turn: usize) -> Action {
    |               ^^^^^ help: if this is intentional, prefix it with an underscore: `_input`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: fields `n` and `people` are never read
   --> Main.rs:108:5
    |
107 | struct Input {
    |        ----- fields in this struct
108 |     n: usize,
    |     ^
109 |     t: usize,
110 |     people: Vec<Person>,
    |     ^^^^^^
    |
    = note: `Input` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis
    = note: `#[warn(dead_code)]` on by default

warning: fields `home` and `company` are never read
   --> Main.rs:132:5
    |
131 | struct Person {
    |        ------ fields in this struct
132 |     home: Coordinate,
    |     ^^^^
133 |     company: Coordinate,
    |     ^^^^^^^
    |
    = note: `Person` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis

warning: variant `Money` is never constructed
   --> Main.rs:188:5
    |
185 | enum Action {
    |      ------ variant in this enum
...
188 |     Money,
    |     ^^^^^

warning: struct `Xoshiro256` is never constructed
   --> Main.rs:455:23
    |
455 |     pub(crate) struct Xoshiro256 {
    |                       ^^^^^^^^^^

warning: function `split_mix_64` is never used
   --> Main.rs:510:8
    |
510 |     fn split_mix_64(x: &mut u64) -> u64 {
    |        ^^^^^^^^^^^^

warning: associated function `new` is never used
   --> Main.rs:463:23
    |
463 |         pub(crate) fn new(mut seed: u64) -> Self {
    |                       ^^^

warning: associated function `next` is never used
   --> Main.rs:

ソースコード

diff # 

use std::{
    fmt::Display,
    io::{stdout, Write},
};

use grid::{inv, Coordinate, Map2d, ADJACENTS};

use crate::rand::Xoshiro256;

macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

#[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),+))
    }};
}

const N: usize = 14;

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    t: usize,
    people: Vec<Person>,
}

impl Input {
    fn read_input() -> Input {
        let (n, t) = get!(usize, usize);
        let mut people = vec![];

        for _ in 0..n {
            let (r0, c0, r1, c1) = get!(usize, usize, usize, usize);
            people.push(Person::new(
                Coordinate::new(r0 - 1, c0 - 1),
                Coordinate::new(r1 - 1, c1 - 1),
            ));
        }

        Input { n, t, people }
    }
}

#[derive(Debug, Clone, Copy)]
struct Person {
    home: Coordinate,
    company: Coordinate,
}

impl Person {
    fn new(home: Coordinate, company: Coordinate) -> Self {
        Self { home, company }
    }
}

#[derive(Debug, Clone)]
struct State {
    money: i64,
    collaborator: i64,
    map: Map2d<[bool; 4]>,
}

impl State {
    fn init() -> Self {
        let map = Map2d::new(vec![[false; 4]; N * N], N);
        Self {
            money: 1000000,
            collaborator: 1,
            map,
        }
    }

    fn calc_construction_cost(&self) -> i64 {
        for i in 1..100 {
            if i * i == self.collaborator {
                return 10_000_000 / i;
            }
        }

        (1e7 / (self.collaborator as f64).sqrt()).floor() as i64
    }

    fn can_construct(&self) -> bool {
        self.money >= self.calc_construction_cost()
    }

    fn update(&mut self) {
        let (money, collaborator) = get!(i64, i64);

        if money == -1 && collaborator == -1 {
            panic!();
        }

        self.money = money;
        self.collaborator = collaborator;
    }
}

enum Action {
    Construct(Coordinate, Coordinate),
    Collaboration,
    Money,
}

impl Action {
    fn apply(&self, state: &mut State) {
        if let &Action::Construct(p, q) = self {
            let mut dir = !0;

            for d in 0..4 {
                let adj = ADJACENTS[d];
                let next = p + adj;

                if next == q {
                    dir = d;
                    break;
                }
            }

            state.map[p][dir] = true;
            state.map[q][inv(dir)] = true;
        }
    }
}

impl Display for Action {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Action::Construct(p, q) => write!(
                f,
                "1 {} {} {} {}",
                p.row + 1,
                p.col + 1,
                q.row + 1,
                q.col + 1
            ),
            Action::Collaboration => write!(f, "2"),
            Action::Money => write!(f, "3"),
        }
    }
}

fn main() {
    let input = Input::read_input();
    let mut state = State::init();

    for turn in 0..input.t {
        state.update();
        let action = get_action(&input, &state, turn);
        action.apply(&mut state);
        println!("{}", action);
        stdout().flush().unwrap();
    }
}

fn get_action(input: &Input, state: &State, turn: usize) -> Action {
    if turn >= 350 || !state.can_construct() {
        return Action::Collaboration;
    }

    let mut candidates = vec![];

    for &row in &[2, 6, 11] {
        for col in 2..10 {
            candidates.push((Coordinate::new(row, col), Coordinate::new(row, col + 1)));
        }
    }

    for &col in &[2, 6, 11] {
        for row in 2..10 {
            candidates.push((Coordinate::new(row, col), Coordinate::new(row + 1, col)));
        }
    }

    const CENTER: Coordinate = Coordinate::new(6, 6);
    candidates.sort_unstable();
    candidates.dedup();
    candidates.sort_by_key(|(p, q)| p.dist(&CENTER).min(q.dist(&CENTER)));

    for &(p, q) in &candidates {
        let mut dir = !0;

        for d in 0..4 {
            let adj = ADJACENTS[d];
            let next = p + adj;

            if next == q {
                dir = d;
                break;
            }
        }

        if !state.map[p][dir] {
            return Action::Construct(p, q);
        }
    }

    Action::Collaboration
}

#[allow(dead_code)]
pub mod grid {
    use std::ops::{Div, DivAssign, Mul, MulAssign};

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coordinate {
        pub row: usize,
        pub col: usize,
    }

    impl Coordinate {
        pub const fn new(row: usize, col: usize) -> Self {
            Self { row, col }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.row < size && self.col < size
        }

        pub const fn to_index(&self, size: usize) -> usize {
            self.row * size + self.col
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.row, other.row) + Self::dist_1d(self.col, other.col)
        }

        const fn dist_1d(x0: usize, x1: usize) -> usize {
            (x0 as i64 - x1 as i64).abs() as usize
        }
    }

    impl Mul<usize> for Coordinate {
        type Output = Coordinate;

        fn mul(self, rhs: usize) -> Self::Output {
            Self::new(self.row * rhs, self.col * rhs)
        }
    }

    impl MulAssign<usize> for Coordinate {
        fn mul_assign(&mut self, rhs: usize) {
            self.row *= rhs;
            self.col *= rhs;
        }
    }

    impl Div<usize> for Coordinate {
        type Output = Coordinate;

        fn div(self, rhs: usize) -> Self::Output {
            Self::new(self.row / rhs, self.col / rhs)
        }
    }

    impl DivAssign<usize> for Coordinate {
        fn div_assign(&mut self, rhs: usize) {
            self.row /= rhs;
            self.col /= rhs;
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct CoordinateDiff {
        pub dr: usize,
        pub dc: usize,
    }

    impl CoordinateDiff {
        pub const fn new(dr: usize, dc: usize) -> Self {
            Self { dr, dc }
        }

        pub const fn invert(&self) -> Self {
            Self::new(0usize.wrapping_sub(self.dr), 0usize.wrapping_sub(self.dc))
        }
    }

    impl std::ops::Add<CoordinateDiff> for Coordinate {
        type Output = Coordinate;

        fn add(self, rhs: CoordinateDiff) -> Self::Output {
            Coordinate::new(self.row.wrapping_add(rhs.dr), self.col.wrapping_add(rhs.dc))
        }
    }

    pub const ADJACENTS: [CoordinateDiff; 4] = [
        CoordinateDiff::new(!0, 0),
        CoordinateDiff::new(0, 1),
        CoordinateDiff::new(1, 0),
        CoordinateDiff::new(0, !0),
    ];

    pub const DIRECTIONS: [char; 4] = ['U', 'R', 'D', 'L'];

    pub fn inv(dir: usize) -> usize {
        dir ^ 2
    }

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        pub width: usize,
        pub height: usize,
        map: Vec<T>,
    }

    impl<T> Map2d<T> {
        pub fn new(map: Vec<T>, width: usize) -> Self {
            let height = map.len() / width;
            debug_assert!(width * height == map.len());
            Self { width, height, map }
        }
    }

    impl<T> std::ops::Index<Coordinate> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: Coordinate) -> &Self::Output {
            &self.map[coordinate.row * self.width + coordinate.col]
        }
    }

    impl<T> std::ops::IndexMut<Coordinate> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coordinate: Coordinate) -> &mut Self::Output {
            &mut self.map[coordinate.row * self.width + coordinate.col]
        }
    }

    impl<T> std::ops::Index<&Coordinate> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coordinate: &Coordinate) -> &Self::Output {
            &self.map[coordinate.row * self.width + coordinate.col]
        }
    }

    impl<T> std::ops::IndexMut<&Coordinate> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coordinate: &Coordinate) -> &mut Self::Output {
            &mut self.map[coordinate.row * self.width + coordinate.col]
        }
    }

    impl<T> std::ops::Index<usize> for Map2d<T> {
        type Output = [T];

        #[inline]
        fn index(&self, row: usize) -> &Self::Output {
            let begin = row * self.width;
            let end = begin + self.width;
            &self.map[begin..end]
        }
    }

    impl<T> std::ops::IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, row: usize) -> &mut Self::Output {
            let begin = row * self.width;
            let end = begin + self.width;
            &mut self.map[begin..end]
        }
    }
}

mod rand {
    pub(crate) struct Xoshiro256 {
        s0: u64,
        s1: u64,
        s2: u64,
        s3: u64,
    }

    impl Xoshiro256 {
        pub(crate) fn new(mut seed: u64) -> Self {
            let s0 = split_mix_64(&mut seed);
            let s1 = split_mix_64(&mut seed);
            let s2 = split_mix_64(&mut seed);
            let s3 = split_mix_64(&mut seed);
            Self { s0, s1, s2, s3 }
        }

        fn next(&mut self) -> u64 {
            let result = (self.s1 * 5).rotate_left(7) * 9;
            let t = self.s1 << 17;

            self.s2 ^= self.s0;
            self.s3 ^= self.s1;
            self.s1 ^= self.s2;
            self.s0 ^= self.s3;
            self.s2 ^= t;
            self.s3 = self.s3.rotate_left(45);

            result
        }

        pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u64) as usize + lower
        }

        pub(crate) fn gen_i32(&mut self, lower: i32, upper: i32) -> i32 {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u64) as i32 + lower
        }

        pub(crate) fn gen_f64(&mut self) -> f64 {
            const UPPER_MASK: u64 = 0x3ff0000000000000;
            const LOWER_MASK: u64 = 0xfffffffffffff;
            let result = UPPER_MASK | (self.next() & LOWER_MASK);
            let result: f64 = unsafe { std::mem::transmute(result) };
            result - 1.0
        }

        pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
            self.gen_f64() < prob
        }
    }

    fn split_mix_64(x: &mut u64) -> u64 {
        *x += 0x9e3779b97f4a7c15;
        let mut z = *x;
        z = (z ^ z >> 30) * 0xbf58476d1ce4e5b9;
        z = (z ^ z >> 27) * 0x94d049bb133111eb;
        return z ^ z >> 31;
    }
}
0