#864455 (Rust) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: 👑 terry_u16
• 提出日時: 2023-04-29 15:05:29
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 17,509 bytes
• コンパイル時間: 1,950 ms
• コンパイル使用メモリ: 167,572 KB
• 実行使用メモリ: 25,404 KB
• スコア: 0
• 最終ジャッジ日時: 2023-04-29 15:05:45
• 合計ジャッジ時間: 9,475 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

ファイルパターン	結果
other	TLE * 1 -- * 49

コンパイルメッセージ

warning: unused import: `OnlineJudge`
 --> Main.rs:5:13
  |
5 | use judge::{OnlineJudge, SelfJudge};
  |             ^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `rand::Xoshiro256`
 --> Main.rs:7:27
  |
7 | use crate::{judge::Judge, rand::Xoshiro256};
  |                           ^^^^^^^^^^^^^^^^

warning: unused import: `std::io::Write`
 --> Main.rs:2:5
  |
2 | use std::io::Write;
  |     ^^^^^^^^^^^^^^

warning: unused variable: `input`
   --> Main.rs:251:15
    |
251 | 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: field `n` is never read
   --> Main.rs:128:5
    |
127 | struct Input {
    |        ----- field in this struct
128 |     n: usize,
    |     ^
    |
    = 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: struct `Xoshiro256` is never constructed
   --> Main.rs:619:23
    |
619 |     pub(crate) struct Xoshiro256 {
    |                       ^^^^^^^^^^

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

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

warning: associated function `next` is never used
   --> Main.rs:635:12
    |
635 |         fn next(&mut self) -> u64 {
    |            ^^^^

warning: associated function `gen_usize` is never used
   --> Main.rs:649:23
    |
649 |         pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
    |                       ^^^^^^^^^

warning: associated function `gen_i32` is never used
   --> Main.rs:655:23
    |

ソースコード

use std::fmt::Display;
use std::io::Write;

use grid::{inv, Coordinate, Map2d, ADJACENTS};
use judge::{OnlineJudge, SelfJudge};

use crate::{judge::Judge, rand::Xoshiro256};

pub trait ChangeMinMax {
    fn change_min(&mut self, v: Self) -> bool;
    fn change_max(&mut self, v: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn change_min(&mut self, v: T) -> bool {
        *self > v && {
            *self = v;
            true
        }
    }

    fn change_max(&mut self, v: T) -> bool {
        *self < v && {
            *self = v;
            true
        }
    }
}

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()
    }
}

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 mut state = State::init();
    let mut judge = SelfJudge::new();
    let input = judge.read_input();

    for turn in 0..input.t {
        judge.update_state(&mut state);
        let action = get_action(&input, &state, turn);
        action.apply(&mut state);
        judge.apply(action);
    }
}

fn get_action(input: &Input, state: &State, turn: usize) -> Action {
    if turn < 70 {
        return Action::Collaboration;
    }

    if turn >= 350 || !state.can_construct() {
        return Action::Money;
    }

    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::Money
}

mod judge {
    use std::{
        cmp::Reverse,
        collections::BinaryHeap,
        io::{stdout, Write},
    };

    use crate::{
        grid::{inv, Coordinate, Map2d, ADJACENTS},
        Action, ChangeMinMax, Input, State, N,
    };

    pub(crate) trait Judge {
        fn read_input(&mut self) -> Input;
        fn update_state(&mut self, state: &mut State);
        fn apply(&mut self, action: Action);
    }

    pub(crate) struct OnlineJudge;

    impl Judge for OnlineJudge {
        fn read_input(&mut self) -> Input {
            Input::read_input()
        }

        fn update_state(&mut self, state: &mut State) {
            let (money, collaborator) = get!(i64, i64);

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

            state.money = money;
            state.collaborator = collaborator;
        }

        fn apply(&mut self, action: Action) {
            println!("{}", action);
            stdout().flush().unwrap();
        }
    }

    pub(crate) struct SelfJudge {
        input: Input,
        state: State,
        turn: usize,
    }

    impl SelfJudge {
        pub(crate) fn new() -> Self {
            let input = Input {
                n: 0,
                t: 0,
                people: vec![],
            };
            let state = State::init();
            Self {
                input,
                state,
                turn: 0,
            }
        }
    }

    impl Judge for SelfJudge {
        fn read_input(&mut self) -> Input {
            self.input = Input::read_input();
            self.input.clone()
        }

        fn update_state(&mut self, state: &mut State) {
            self.turn += 1;
            eprintln!("[TURN {:3}]", self.turn);

            let mut distances = Map2d::new(vec![Map2d::new(vec![], N); N * N], N);

            for row0 in 0..N {
                for col0 in 0..N {
                    let mut dists = Map2d::new(vec![std::i32::MAX / 2; N * N], N);
                    let mut queue = BinaryHeap::new();
                    dists[Coordinate::new(row0, col0)] = 0;
                    queue.push(Reverse((0, Coordinate::new(row0, col0))));

                    while let Some(Reverse((dist, c))) = queue.pop() {
                        if dist > dists[c] {
                            continue;
                        }

                        for dir in 0..4 {
                            let next = c + ADJACENTS[dir];
                            let next_cost = dist + if self.state.map[c][dir] { 223 } else { 1000 };

                            if next.in_map(N) && dists[next].change_min(next_cost) {
                                queue.push(Reverse((next_cost, next)));
                            }
                        }
                    }

                    distances[Coordinate::new(row0, col0)] = dists;
                }
            }

            for &person in &self.input.people {
                let dist = distances[person.home][person.company];

                for count in 0.. {
                    let remain = dist - 223 * count;
                    if remain % 1000 == 0 {
                        self.state.money += 60 * count as i64;
                        break;
                    }
                }
            }

            eprintln!("money: {}", self.state.money);

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

        fn apply(&mut self, action: Action) {
            eprintln!("action: {}", action);

            match action {
                Action::Construct(p, q) => {
                    let cost = self.state.calc_construction_cost();
                    if self.state.money < cost {
                        panic!();
                    }

                    self.state.money -= cost;

                    for dir in 0..4 {
                        if p + ADJACENTS[dir] == q {
                            self.state.map[p][dir] = true;
                            self.state.map[q][inv(dir)] = true;
                            return;
                        }
                    }
                }
                Action::Collaboration => {
                    self.state.collaborator += 1;
                }
                Action::Money => {
                    self.state.money += 50000;
                }
            }
        }
    }
}

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