結果
| 問題 |
No.5019 Hakai Project
|
| コンテスト | |
| ユーザー |
 human
|
| 提出日時 | 2023-11-18 20:38:06 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2,792 ms / 3,000 ms |
| コード長 | 30,165 bytes |
| コンパイル時間 | 4,032 ms |
| コンパイル使用メモリ | 208,924 KB |
| 実行使用メモリ | 385,792 KB |
| スコア | 2,237,466,546 |
| 最終ジャッジ日時 | 2023-11-18 20:40:37 |
| 合計ジャッジ時間 | 150,730 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#![allow(dead_code)]
#![allow(non_upper_case_globals)]
#![allow(unused_imports)]
use grid::{Coord, Map2d, DC};
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use self::rnd::shuffle;
const TIME_LIMIT: f64 = 2.7;
const N: usize = 50;
const N2: usize = N * N;
const M: usize = 20;
pub fn main() {
get_time();
let input = read_input();
let output = solve(&input);
output.print_ans();
eprintln!("Time = {}", get_time());
}
fn solve(input: &Input) -> Output {
let state = loop {
let mut state = State::new(input);
state.calc_score_2(input);
if state.score < usize::MAX / 3 {
break state;
}
};
annealing(input, TIME_LIMIT - get_time(), state).to_output_2(input)
}
#[derive(Clone)]
struct State {
score: usize,
use_bomb: Map2d<Vec<bool>>,
cnt_use: Map2d<usize>,
jun: Vec<(Coord, usize)>,
}
impl State {
fn new(input: &Input) -> Self {
let score = !0;
let mut use_bomb = Map2d::new(vec![vec![false; M]; N2], N);
let mut cnt_use = Map2d::new(vec![0; N2], N);
let mut jun = vec![];
let mut pvec = vec![];
let mut pvec2 = vec![];
for x in 0..N {
for y in 0..N {
if 5 < x && x < N - 5 && 5 < y && y < N - 5 {
pvec.push(Coord::new(x, y));
} else {
pvec2.push(Coord::new(x, y));
}
}
}
rnd::shuffle(&mut pvec);
rnd::shuffle(&mut pvec2);
pvec.extend(pvec2);
for p in pvec {
if input.map[p] == Square::Empty || cnt_use[p] > 0 {
continue;
}
if let Some(&(bp, bid)) = input.can_hakai_rev[p]
.iter()
.find(|&&bp| 5 < bp.0.x && bp.0.x < N - 5 && 5 < bp.0.y && bp.0.y < N - 5)
{
use_bomb[bp][bid] = true;
for &np in input.can_hakai[bp][bid].iter() {
cnt_use[np] += 1;
}
jun.push((bp, bid));
} else {
let (bp, bid) = input.can_hakai_rev[p][rnd::next() % input.can_hakai_rev[p].len()];
use_bomb[bp][bid] = true;
for &np in input.can_hakai[bp][bid].iter() {
cnt_use[np] += 1;
}
jun.push((bp, bid));
}
}
Self {
score,
use_bomb,
cnt_use,
jun,
}
}
fn calc_score(&mut self, input: &Input) {
let mut score = 0;
let sz = self.jun.len();
// uso dp
let mut dp = 0;
let mut rui = 0;
let mut mae = Coord::new(0, 0);
let mut bombed = Map2d::new(vec![false; N2], N);
for i in 0..sz {
score += input.bomb_cost[self.jun[i].1];
let ue = if i == 0 {
(!0, !0)
} else {
(
dp + rui + self.jun[i].0.dist(&mae),
1 * (rui + self.jun[i].0.dist(&mae)),
)
};
let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
{
(
dp + mae.dist(&near) + self.jun[i].0.dist(&near),
1 * (self.jun[i].0.dist(&near)),
)
} else {
(!0, !0)
};
if ue.0 < sita.0 {
dp = ue.0;
rui = ue.1;
} else {
dp = sita.0;
rui = sita.1;
}
mae = self.jun[i].0;
for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
bombed[np] = true;
}
}
self.score = score + dp;
}
fn calc_score_2(&mut self, input: &Input) {
let mut score = 0;
let sz = self.jun.len();
// uso dp
// 前から
let max_size = 3;
let mut dp = vec![vec![usize::MAX; max_size]; sz + 1];
dp[0][0] = 0;
let mut bombed = Map2d::new(vec![false; N2], N);
for i in 0..sz {
score += 5 * input.bomb_cost[self.jun[i].1];
// 購入する場合0->j
if dp[i][0] != usize::MAX {
if let Some(&near) = input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
{
for j in 0..max_size {
let cost = if i == 0 {
dp[i][0]
+ 1 * Coord::new(0, 0).dist(&near)
+ 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
} else {
dp[i][0]
+ 1 * self.jun[i - 1].0.dist(&near)
+ 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
};
dp[i + 1][j] = dp[i + 1][j].min(cost);
}
}
}
// 購入しない場合
for j in 1..max_size {
if dp[i][j] == usize::MAX {
continue;
}
let cost =
dp[i][j] + 1 * (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
dp[i + 1][j - 1] = dp[i + 1][j - 1].min(cost);
}
for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
bombed[np] = true;
}
}
if dp[sz][0] == usize::MAX {
self.score = usize::MAX / 2;
} else {
self.score = score + dp[sz][0];
}
}
fn calc_score_3(&mut self, input: &Input) {
// バグっている
let mut score = 0;
let sz = self.jun.len();
// uso dp
// 前から
let max_size = 3;
let mut dp = vec![vec![usize::MAX; max_size]; 2];
dp[0][0] = 0;
let mut bombed = Map2d::new(vec![false; N2], N);
for i in 0..sz {
score += 5 * input.bomb_cost[self.jun[i].1];
// 購入する場合0->j
if dp[i % 2][0] != usize::MAX {
if let Some(&near) = input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
{
for j in 0..max_size {
let cost = if i == 0 {
dp[i % 2][0]
+ 1 * Coord::new(0, 0).dist(&near)
+ 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
} else {
dp[i % 2][0]
+ 1 * self.jun[i - 1].0.dist(&near)
+ 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
};
dp[(i + 1) % 2][j] = dp[(i + 1) % 2][j].min(cost);
}
}
}
// 購入しない場合
for j in 1..max_size {
if dp[i % 2][j] == usize::MAX {
continue;
}
let cost =
dp[i % 2][j] + 1 * (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
dp[(i + 1) % 2][j - 1] = dp[(i + 1) % 2][j - 1].min(cost);
}
for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
bombed[np] = true;
}
}
if dp[(sz + 1) % 2][0] == usize::MAX {
self.score = usize::MAX / 2;
} else {
self.score = score + dp[(sz + 1) % 2][0];
}
}
fn to_output(&self, input: &Input) -> Output {
let mut actions = vec![];
let sz = self.jun.len();
let mut dp = 0;
let mut rui = 0;
let mut mae = Coord::new(0, 0);
let mut bombed = Map2d::new(vec![false; N2], N);
let mut buyvec = vec![];
for i in 0..sz {
let ue = if i == 0 {
(!0, !0)
} else {
(
dp + rui + self.jun[i].0.dist(&mae),
rui + self.jun[i].0.dist(&mae),
)
};
let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
{
(
dp + mae.dist(&near) + self.jun[i].0.dist(&near),
self.jun[i].0.dist(&near),
)
} else {
(!0, !0)
};
if ue.0 < sita.0 {
dp = ue.0;
rui = ue.1;
actions.extend(moves_dijkstra(mae, self.jun[i].0, &bombed, input));
} else {
dp = sita.0;
rui = sita.1;
let near = *input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
.unwrap();
//actions.extend(moves(mae, near));
actions.extend(moves_dijkstra(mae, near, &bombed, input));
// ここに購入を計算 todo // あとでここに入れる
buyvec.push(vec![]);
actions.push((2, !0));
//
//actions.extend(moves(near, self.jun[i].0));
actions.extend(moves_dijkstra(near, self.jun[i].0, &bombed, input));
}
// use
actions.push((3, self.jun[i].1 + 1));
let lll = buyvec.len() - 1;
buyvec[lll].push((2, self.jun[i].1 + 1));
//
mae = self.jun[i].0;
for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
bombed[np] = true;
}
}
let mut ret_actions = vec![];
let mut buyidx = 0;
for &(tp, dd) in actions.iter() {
if tp != 2 {
ret_actions.push((tp, dd));
} else {
for &t in buyvec[buyidx].iter() {
ret_actions.push(t);
}
buyidx += 1;
}
}
Output {
score: self.score,
actions: ret_actions,
}
}
fn to_output_2(&self, input: &Input) -> Output {
let mut actions = vec![];
let sz = self.jun.len();
let max_size = sz + 1;
let mut dp = vec![vec![(usize::MAX, usize::MAX); max_size]; sz + 1];
dp[0][0] = (0, !0);
let mut bombed = Map2d::new(vec![false; N2], N);
for i in 0..sz {
// 購入する場合0->j
if dp[i][0].0 != usize::MAX {
if let Some(&near) = input.near_shop[self.jun[i].0]
.iter()
.find(|&&np| !bombed[np])
{
for j in 0..max_size {
let cost = if i == 0 {
dp[i][0].0
+ Coord::new(0, 0).dist(&near)
+ (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
} else {
dp[i][0].0
+ self.jun[i - 1].0.dist(&near)
+ (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
};
dp[i + 1][j] = dp[i + 1][j].min((cost, 0));
}
}
}
// 購入しない場合
for j in 1..max_size {
if dp[i][j].0 == usize::MAX {
continue;
}
let cost = dp[i][j].0 + (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
dp[i + 1][j - 1] = dp[i + 1][j - 1].min((cost, j));
}
for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
bombed[np] = true;
}
}
// 復元
let mut rireki = vec![];
let mut nowj = 0;
for i in (1..sz + 1).rev() {
// use
rireki.push((3, !0));
let nextnowj = dp[i][nowj].1;
assert!(nextnowj != usize::MAX);
assert!(nowj + 1 >= nextnowj);
if nowj >= nextnowj {
// buy
rireki.push((2, nowj - nextnowj + 1));
}
nowj = nextnowj;
if nowj == usize::MAX {
eprintln!("AAA {} {} {} {}", i, sz, dp[sz][0].0, dp[sz][0].1);
}
}
rireki.reverse();
let mut bombed = Map2d::new(vec![false; N2], N);
let mut mae = Coord::new(0, 0);
let mut idx = 0;
for (tp, d) in rireki {
if tp == 2 {
// buy
let near = *input.near_shop[self.jun[idx].0]
.iter()
.find(|&&np| !bombed[np])
.unwrap();
assert!(input.map[near] == Square::Shop && !bombed[near]);
actions.extend(moves_dijkstra(mae, near, &bombed, input));
for j in 0..d {
actions.push((2, self.jun[idx + j].1 + 1));
}
mae = near;
} else {
// use
actions.extend(moves_dijkstra(mae, self.jun[idx].0, &bombed, input));
mae = self.jun[idx].0;
actions.push((3, self.jun[idx].1 + 1));
for &np in input.can_hakai[self.jun[idx].0][self.jun[idx].1].iter() {
bombed[np] = true;
}
idx += 1;
}
}
Output {
score: self.score,
actions,
}
}
fn add_bomb(&mut self, input: &Input, bp: Coord, bid: usize) {
for &np in input.can_hakai[bp][bid].iter() {
self.cnt_use[np] += 1;
}
}
fn swap_jun(&mut self, pos: (usize, usize)) {
let a = self.jun[pos.0];
self.jun[pos.0] = self.jun[pos.1];
self.jun[pos.1] = a;
}
fn swap_off(&mut self, input: &Input) -> bool {
let idx = rnd::next() % self.jun.len();
let bp = self.jun[idx].0;
let bid = self.jun[idx].1;
let mut added = vec![];
for &np in input.can_hakai[bp][bid].iter() {
self.cnt_use[np] -= 1;
if self.cnt_use[np] == 0 {
let mut revclone = input.can_hakai_rev[np].clone();
rnd::shuffle(&mut revclone);
if let Some(&nb) = revclone.iter().find(|&&ip| !self.use_bomb[ip.0][ip.1]) {
self.add_bomb(input, nb.0, nb.1);
added.push(nb);
self.use_bomb[nb.0][nb.1] = true;
} else {
return false;
}
}
}
self.use_bomb[bp][bid] = false;
self.jun.remove(idx);
for nb in added {
let mut min_cost = !0;
let mut best_idx = !0;
for i in 0..self.jun.len() {
let dist = if i == 0 {
Coord::new(0, 0).dist(&nb.0) + nb.0.dist(&self.jun[i].0)
} else {
self.jun[i - 1].0.dist(&nb.0) + nb.0.dist(&self.jun[i].0)
};
if min_cost > dist {
min_cost = dist;
best_idx = i;
}
}
self.jun.insert(best_idx, nb);
}
true
}
fn insert_jun(&mut self) {
let bb = rnd::next() % self.jun.len();
let b = self.jun[bb];
self.jun.remove(bb);
let mut min_cost = !0;
let mut best_idx = !0;
for i in 0..self.jun.len() {
let dist = if i == 0 {
Coord::new(0, 0).dist(&b.0) + b.0.dist(&self.jun[i].0)
} else {
self.jun[i - 1].0.dist(&b.0) + b.0.dist(&self.jun[i].0)
};
if min_cost > dist {
min_cost = dist;
best_idx = i;
}
}
self.jun.insert(best_idx, b);
}
}
fn annealing(input: &Input, duration: f64, mut state: State) -> State {
let start_time = get_time();
let duration_inv = 1.0 / duration;
const START_TEMP: f64 = 1000.0;
const END_TEMP: f64 = 1.1;
const DIFF_TEMP: f64 = END_TEMP / START_TEMP;
let mut temp = START_TEMP;
let update_temp = || {
// 非線形
return START_TEMP * DIFF_TEMP.powf((get_time() - start_time) * duration_inv);
// 線形
//return START_TEMP + (END_TEMP - START_TEMP) * (get_time() - start_time) * duration_inv;
};
let loglis = (0..0x10000)
.map(|i| (i as f64 / 0xffff as f64).ln())
.collect::<Vec<_>>();
fn is_accepted(now_score: usize, next_score: usize, temp: f64, loglis: &Vec<f64>) -> bool {
// 最大化する場合。最小化時は -(next_score - now_score)
-(next_score as f64 - now_score as f64) >= temp * loglis[rnd::next() & 0xffff]
}
let mut best_state = state.clone();
let mut iter_sa = 0;
let mut cnt_kousin = 0;
let mut cnt_kousin_best = 0;
loop {
if iter_sa & 255 == 0 {
if get_time() - start_time > duration {
break;
}
// kick! if mae_kousin > 100 {}
temp = update_temp();
}
iter_sa += 1;
let op = rnd::next() % 100;
if op < 60 {
let now_score = state.score;
let pos = select_2(state.jun.len());
state.swap_jun(pos);
state.calc_score_2(input);
let next_score = state.score;
if is_accepted(now_score, next_score, temp, &loglis) {
cnt_kousin += 1;
} else {
state.swap_jun(pos);
state.score = now_score;
}
} else if op < 1 {
let now_score = state.score;
let mut next_state = state.clone();
next_state.insert_jun();
next_state.calc_score_2(input);
let next_score = next_state.score;
if is_accepted(now_score, next_score, temp, &loglis) {
cnt_kousin += 1;
state = next_state;
} else {
//
}
} else {
let now_score = state.score;
let mut next_state = state.clone();
let ss = next_state.swap_off(input);
if !ss {
continue;
}
next_state.calc_score_2(input);
let next_score = next_state.score;
if is_accepted(now_score, next_score, temp, &loglis) {
cnt_kousin += 1;
state = next_state;
} else {
//
}
}
if best_state.score > state.score {
best_state = state.clone();
cnt_kousin_best += 1;
}
}
crate::print_data!(iter_sa);
crate::print_data!(cnt_kousin);
crate::print_data!(cnt_kousin_best);
best_state
}
fn moves(a: Coord, b: Coord) -> Vec<(usize, usize)> {
let mut ret = vec![];
let mut p = a;
while p != b {
if p.y > b.y {
p.y -= 1;
ret.push((1, 0));
} else if p.x > b.x {
p.x -= 1;
ret.push((1, 1));
} else if p.y < b.y {
p.y += 1;
ret.push((1, 2));
} else if p.x < b.x {
p.x += 1;
ret.push((1, 3));
};
}
ret
}
fn moves_dijkstra(a: Coord, b: Coord, bombed: &Map2d<bool>, input: &Input) -> Vec<(usize, usize)> {
let mut ret = vec![];
if a == b {
return ret;
}
let mut dp = Map2d::new(vec![(!0usize, !0); N2], N);
dp[a] = (0, !0);
let mut que = BinaryHeap::new();
que.push((Reverse(0), a));
while let Some((Reverse(dist), p)) = que.pop() {
if que.len() > 10000 {
assert!(1 == 0);
}
if p == b {
break;
}
for dir in 0..4 {
let np = p.next(dir);
if !np.in_map(N) {
continue;
}
let ncost = if input.map[np] == Square::Empty || bombed[np] {
dist + 1
} else {
dist + 2
};
if ncost < dp[np].0 {
dp[np] = (ncost, dir);
que.push((Reverse(ncost), np));
}
}
}
assert!(dp[b].1 != !0);
let mut p = b;
while p != a {
ret.push((1, dp[p].1));
p = p.next((2 + dp[p].1) % 4);
}
ret.reverse();
ret
}
fn calc_dist_dijkstra(a: Coord, b: Coord, bombed: &Map2d<bool>, input: &Input) -> usize {
let mut dp = Map2d::new(vec![!0usize; N2], N);
dp[a] = 0;
let mut que = BinaryHeap::new();
que.push((Reverse(0), a));
while let Some((Reverse(dist), p)) = que.pop() {
if p == b {
return dist;
}
if dist > dp[p] {
continue;
}
for dir in 0..4 {
let np = p.next(dir);
if !np.in_map(N) {
continue;
}
let ncost = if input.map[np] == Square::Empty || bombed[np] {
dist + 1
} else {
dist + 2
};
if ncost < dp[np] {
dp[np] = ncost;
que.push((Reverse(ncost), np));
}
}
}
unreachable!()
}
#[derive(PartialEq, Eq, Clone, Copy)]
enum Square {
Empty,
House,
Shop,
}
struct Input {
map: Map2d<Square>,
bomb_cost: Vec<usize>,
near_shop: Map2d<Vec<Coord>>,
can_hakai: Map2d<Vec<Vec<Coord>>>, // そのマスで爆弾iを使って破壊できるもの
can_hakai_rev: Map2d<Vec<(Coord, usize)>>, // そのマスを破壊することができるマスと爆弾の種類
}
fn read_input() -> Input {
let _nm = input_vecusize();
let mut map_ = vec![];
for _i in 0..N {
let a = input_string();
map_.push(a.chars().collect::<Vec<_>>());
}
let mut map = vec![];
for x in 0..N {
for y in 0..N {
let c = match map_[x][y] {
'.' => Square::Empty,
'#' => Square::House,
'@' => Square::Shop,
_ => unreachable!(),
};
map.push(c);
}
}
let map = Map2d::new(map, N);
let mut can_hakai = Map2d::new(vec![vec![vec![]; M]; N2], N);
let mut bomb_cost = vec![];
let mut can_hakai_rev = Map2d::new(vec![vec![]; N2], N);
for bombid in 0..M {
let cl = input_vecusize();
let c = cl[0];
let l = cl[1];
bomb_cost.push(c);
for _ in 0..l {
let dxdy = input_veci32();
let dx = dxdy[0];
let dy = dxdy[1];
for x in 0..N as i32 {
for y in 0..N as i32 {
let nx = x + dx;
let ny = y + dy;
let p = Coord::new(x as usize, y as usize);
let np = Coord::new(nx as usize, ny as usize);
if 0 <= nx
&& nx < N as i32
&& 0 <= ny
&& ny < N as i32
&& map[np] != Square::Empty
{
can_hakai[p][bombid].push(np);
can_hakai_rev[np].push((p, bombid));
}
}
}
}
}
let mut near_shop = Map2d::new(vec![vec![]; N2], N);
let mut shops = vec![];
for x in 0..N {
for y in 0..N {
let p = Coord::new(x, y);
if map[p] == Square::Shop {
shops.push(p);
}
}
}
for x in 0..N {
for y in 0..N {
let p = Coord::new(x, y);
near_shop[p] = shops.clone();
near_shop[p].sort_by(|a, b| p.dist(a).cmp(&p.dist(b)));
}
}
Input {
map,
bomb_cost,
near_shop,
can_hakai,
can_hakai_rev,
}
}
struct Output {
score: usize,
actions: Vec<(usize, usize)>,
}
impl Output {
fn print_ans(&self) {
//let cost = self.score;
//crate::print_data!(cost);
//let score = 1000000000000usize / (10000 + cost);
//crate::print_data!(score);
let q = self.actions.len();
println!("{}", q);
for i in 0..q {
if self.actions[i].0 == 1 {
println!("{} {}", self.actions[i].0, DC[self.actions[i].1]);
} else {
println!("{} {}", self.actions[i].0, self.actions[i].1);
}
}
}
}
// ここからライブラリ
#[macro_export]
macro_rules! print_data {
( $($x:expr),* ) => {{
$(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)*
}}
}
pub fn get_time() -> f64 {
static mut START: f64 = -1.0;
let end = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap()
.as_secs_f64();
unsafe {
if START < 0.0 {
START = end;
}
end - START
}
}
#[allow(unused)]
mod rnd {
static mut S: usize = 88172645463325252;
pub fn next() -> usize {
unsafe {
S ^= S << 7;
S ^= S >> 9;
S
}
}
pub fn nextf() -> f64 {
f64::from_bits((0x3ff0000000000000 | next() & 0xfffffffffffff) as u64) - 1.
}
pub fn range(a: usize, b: usize) -> usize {
next() % (b - a) + a
}
pub fn exu(a: usize, b: usize, skip: usize) -> usize {
assert!(a <= skip && skip < b);
let ret = range(a, b - 1);
ret + (skip <= ret) as usize
}
pub fn rangei(a: i64, b: i64) -> i64 {
(next() % ((b - a) as usize)) as i64 + a
}
pub fn shuffle<T>(list: &mut [T]) {
for i in (0..list.len()).rev() {
list.swap(i, next() % (i + 1));
}
}
}
#[allow(dead_code)]
mod grid {
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Coord {
pub x: usize,
pub y: usize,
}
impl Coord {
pub const fn new(x: usize, y: usize) -> Self {
Self { x, y }
}
pub const fn new2(p: usize, width: usize) -> Self {
Self {
x: p / width,
y: p % width,
}
}
pub fn in_map(&self, size: usize) -> bool {
self.x < size && self.y < size
}
pub const fn idx(&self, size: usize) -> usize {
self.x * size + self.y
}
pub fn next(self, dir: usize) -> Self {
self + DXY[dir]
}
pub const fn dist(&self, other: &Self) -> usize {
Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y)
}
const fn dist_1d(x0: usize, x1: usize) -> usize {
x0.abs_diff(x1)
}
}
impl std::ops::Add for Coord {
type Output = Self;
fn add(self, other: Self) -> Self {
Self {
x: self.x + other.x,
y: self.y + other.y,
}
}
}
pub const DXY: [Coord; 4] = [
Coord::new(0, !0),
Coord::new(!0, 0),
Coord::new(0, 1),
Coord::new(1, 0),
];
pub const DC: [char; 4] = ['L', 'U', 'R', 'D'];
#[derive(Debug, Clone)]
pub struct Map2d<T> {
pub height: usize,
pub width: usize,
map: Vec<T>,
}
impl<T: Clone> Map2d<T> {
pub fn new(map: Vec<T>, width: usize) -> Self {
let height = map.len() / width;
debug_assert!(width * height == map.len());
Self { height, width, map }
}
pub fn fill(&mut self, value: T) {
self.map.fill(value);
}
}
impl<T> std::ops::Index<Coord> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, coord: Coord) -> &Self::Output {
unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) }
}
}
impl<T> std::ops::IndexMut<Coord> for Map2d<T> {
#[inline]
fn index_mut(&mut self, coord: Coord) -> &mut Self::Output {
unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) }
}
}
impl<T> std::ops::Index<&Coord> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, coord: &Coord) -> &Self::Output {
&self.map[coord.x * self.width + coord.y]
}
}
impl<T> std::ops::IndexMut<&Coord> for Map2d<T> {
#[inline]
fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output {
&mut self.map[coord.x * self.width + coord.y]
}
}
impl<T> std::ops::Index<usize> for Map2d<T> {
type Output = T;
#[inline]
fn index(&self, p: usize) -> &Self::Output {
&self.map[p]
}
}
impl<T> std::ops::IndexMut<usize> for Map2d<T> {
#[inline]
fn index_mut(&mut self, p: usize) -> &mut Self::Output {
&mut self.map[p]
}
}
}
fn input_vecusize() -> Vec<usize> {
let mut a = String::new();
stdin().read_line(&mut a).unwrap();
return a
.trim()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect();
}
fn input_veci32() -> Vec<i32> {
let mut a = String::new();
stdin().read_line(&mut a).unwrap();
return a
.trim()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect();
}
fn input_string() -> String {
let mut a = String::new();
stdin().read_line(&mut a).unwrap();
return a.trim().parse().unwrap();
}
fn select_2(r: usize) -> (usize, usize) {
let a = rnd::next() % r;
let b = rnd::exu(0, r, a);
(a, b)
}