結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 terry_u16
|
| 提出日時 | 2023-04-29 15:05:29 |
| 言語 | Rust (1.77.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_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;
}
}