結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 fumin29
|
| 提出日時 | 2025-07-26 16:26:27 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,569 ms / 2,000 ms |
| コード長 | 35,032 bytes |
| コンパイル時間 | 15,987 ms |
| コンパイル使用メモリ | 399,116 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,130,338,792 |
| 最終ジャッジ日時 | 2025-07-26 16:27:47 |
| 合計ジャッジ時間 | 78,634 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
warning: field `io` is never read
--> src/main.rs:33:5
|
32 | struct Solver<'a> {
| ------ field in this struct
33 | io: &'a Io,
| ^^
|
= note: `#[warn(dead_code)]` on by default
warning: methods `find_nearest_k2` and `find_paths_to_write` are never used
--> src/main.rs:109:8
|
37 | impl<'a> Solver<'a> {
| ------------------- methods in this implementation
...
109 | fn find_nearest_k2(&self, pos: P, k: u32, s: u32) -> Option<P> {
| ^^^^^^^^^^^^^^^
...
141 | fn find_paths_to_write(&self, pos:P, k:u32, s:u32) -> Vec<P> {
| ^^^^^^^^^^^^^^^^^^^
ソースコード
#![allow(unused_imports, non_camel_case_types)]
use std::{*, collections::*, ops::*, cmp::*, iter::*};
use fumin::{grid_v::GridV, pt::Dir};
use proconio::{input, fastout};
use common::*;
fn main() {
solve();
}
const N: us = 10;
const T: us = 1000;
type P = fumin::pt::Pt<us>;
struct Io {
_n: us,
_t: us,
a: GridV<u32>,
}
impl Io {
fn new() -> Self {
input! {n:us,t:us,a:[[u32;n];n]}
Self {
_n: n,
_t: t,
a: GridV::from(&a),
}
}
}
struct Solver<'a> {
io: &'a Io,
a: GridV<u32>,
}
impl<'a> Solver<'a> {
fn new(io: &'a Io) -> Self {
Self {
io,
a: io.a.clone(),
}
}
fn solve(&mut self) -> Vec<char> {
let mut pos = P::new(0,0);
let mut ans = vec![];
let mut s = 0;
for k in (0..21).rev() {
if ans.len() > T { break; }
let Some(t) = self.find_nearest_k(pos, k, s) else { continue };
if t != P::INF {
ans.extend(P::to_dirs(&P::move_xy(pos, t)).map(|d|d.c()));
ans.push('C');
s ^= self.a[t];
pos = t;
}
let cand = self.find_paths_to_write2(pos, k, s);
for (i,nv) in cand.clone().into_iter().enumerate() {
ans.extend(P::to_dirs(&P::move_xy(pos, nv)).map(|d|d.c()));
if i == cand.len() - 1 {
ans.push('C');
s ^= self.a[nv];
} else {
ans.push('W');
self.a[nv] ^= s;
}
pos = nv;
}
// eprintln!("{}: s={:020b}", k, s);
// for i in 0..N {
// eprintln!("{:?}", self.a[i].map(|&x|format!("{:020b}", x)));
// }
}
ans.truncate(T);
ans
}
fn find_nearest_k(&self, pos: P, k: u32, s: u32) -> Option<P> {
// if s>>k&1 == 1 {
// return Some(P::INF);
// }
let a = &self.a;
let mut q = deque::new();
let mut vis = GridV::with_default(N, N, false);
vis[pos] = true;
q.push(pos);
while let Some(v) = q.pop_front() {
let ns = a[v]^s;
if ns>>(k+1)&1==0 && ns>>k&1==1 {
// if self.a[v]>>k&1 == 1 {
return Some(v);
}
for d in Dir::VAL4 {
let nv = v.next(d);
if a.is_in_p(nv) && !vis[nv] {
vis[nv] = true;
q.push(nv);
}
}
}
None
}
fn find_nearest_k2(&self, pos: P, k: u32, s: u32) -> Option<P> {
// aのkビット目より大きいビットは全て立っている前提
// また、sはk+1ビット目が1, それより大きいビットは0になっている前提
// sをkビット目は1, それより大きいビットは0になるようなセルを見つける
// s=01***, k=2の場合、s=001**になるようなaを見つけたい。aの上位ビットは11になってるので、偶数回コピーする必要がある
// a1=11
// つまり、s[k]^a[k]==0のばあい、a[k]==1
if s>>k&1 == 1 {
return Some(P::INF);
}
let a = &self.a;
let mut q = deque::new();
let mut vis = GridV::with_default(N, N, false);
vis[pos] = true;
q.push(pos);
while let Some(v) = q.pop_front() {
if self.a[v]>>k&1 == 1 {
return Some(v);
}
for d in Dir::VAL4 {
let nv = v.next(d);
if a.is_in_p(nv) && !vis[nv] {
vis[nv] = true;
q.push(nv);
}
}
}
None
}
fn find_paths_to_write(&self, pos:P, k:u32, s:u32) -> Vec<P> {
// 巡回セールスマン問題を解きたいが、、
let a = &self.a;
let mut cur = pos;
let mut ret = vec![];
let mut vis0 = GridV::with_default(N, N, false);
loop {
let mut q = deque::new();
let mut vis = GridV::with_default(N, N, false);
q.push(cur);
vis[cur] = true;
let mut tt = P::INF;
while let Some(v) = q.pop_front() {
if self.a[v]>>k&1 == 0 && !vis0[v] && self.a[v]^s > self.a[v] {
tt = v;
break;
}
for d in Dir::VAL4 {
let nv = v.next(d);
if a.is_in_p(nv) && !vis[nv] {
vis[nv] = true;
q.push(nv);
}
}
}
if tt == P::INF { break; }
cur = tt;
vis0[tt] = true;
ret.push(tt);
}
eprintln!("{}: {}, {:020b}", k, ret.len(), s);
ret
}
fn find_paths_to_write2(&self, pos:P, k:u32, s:u32) -> Vec<P> {
// 巡回セールスマン問題を解きたいが、、
let a = &self.a;
let mut tt = (0..N).flat_map(|i|(0..N).map(move|j|(i,j)))
.map(|(i,j)|P::new(i,j))
.filter(|&v|a[v]>>k&1==0 && a[v]^s>a[v])
.cbset();
let mut tour = vec![pos];
let mut cur = pos;
while !tt.is_empty() {
let t = tt.iter().min_by_key(|&&v|cur.manhattan_distance(v)).cloned().unwrap();
tour.push(t);
tt.remove(&t);
cur = t;
}
// eprintln!("{}: {}, {:020b}", k, tour.len()-1, s);
// return tour[1..].to_vec();
if tour.len() <= 3 { return tour[1..].to_vec(); }
// 山登り
let n = tour.len();
let mut rng = Xorshift::new();
let mut temp = 400.0; // 初期温度（距離差 ≒400 ならほぼ許容）
let end_temp = 0.1;
let alpha = 0.995; // 冷却率
let iter_per_temp = 30 * n; // 温度ごとの試行回数
// 現在距離
// let mut len = (0..n-1).map(|i|tour[i].manhattan_distance(tour[i+1]).i64()).sum::<i64>();
while temp > end_temp {
for _ in 0..iter_per_temp {
// 2点 (i, j) をランダムに選び (i+1 … j) を反転
let i = rng.rand((n - 2) as u64) as us;
let j = rng.rand((n-(i+2)) as u64) as us + (i + 2);
let a = tour[i];
let b = tour[i+1];
let c = tour[j];
let mut delta = a.manhattan_distance(c).i64() - a.manhattan_distance(b).i64();
if j + 1 < n {
let d = tour[j+1];
delta += b.manhattan_distance(d).i64() - c.manhattan_distance(d).i64();
}
if delta < 0 || rng.randf() < (-(delta as f64) / temp).exp() {
// if delta < 0 {
// 受容：区間反転
tour[(i + 1)..=j].reverse();
// len += delta;
}
}
temp *= alpha;
}
tour[1..].to_vec()
}
fn score(&self) -> u32 {
self.a.g.sum()
}
}
// CONTEST(abcXXX-a)
#[fastout]
fn solve() {
let io = Io::new();
let mut solver = Solver::new(&io);
let ans = solver.solve();
for &c in &ans { println!("{}", c); }
eprintln!("Score = {}", solver.score());
}
// https://qiita.com/hatoo@github/items/652b81e8e83b0680bc0a
#[derive(Debug)]
#[allow(dead_code)]
pub struct Xorshift {
seed: u64,
}
impl Xorshift {
#[allow(dead_code)]
pub fn new() -> Xorshift {
Xorshift {
seed: 0xf0fb588ca2196dac,
}
}
#[allow(dead_code)]
pub fn with_seed(seed: u64) -> Xorshift {
Xorshift { seed: seed }
}
#[inline]
#[allow(dead_code)]
pub fn next(&mut self) -> u64 {
self.seed = self.seed ^ (self.seed << 13);
self.seed = self.seed ^ (self.seed >> 7);
self.seed = self.seed ^ (self.seed << 17);
self.seed
}
#[inline]
#[allow(dead_code)]
pub fn rand(&mut self, m: u64) -> u64 {
self.next() % m
}
#[inline]
#[allow(dead_code)]
// 0.0 ~ 1.0
pub fn randf(&mut self) -> f64 {
use std::mem;
const UPPER_MASK: u64 = 0x3FF0000000000000;
const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { mem::transmute(tmp) };
result - 1.0
}
}
pub mod fumin {
pub mod grid_v {
#![allow(dead_code)]
use std::{ops::{Index, IndexMut}, cmp::Reverse};
use crate::{common::*, chmin};
use super::pt::{Pt, Dir};
#[derive(Debug, Clone)]
pub struct GridV<T> {
pub g: Vec<T>,
h: us,
w: us,
}
impl<T: Clone> GridV<T> {
pub fn with_default(h: us, w: us, v: T) -> Self {
Self { g: vec![v; h * w], h, w, }
}
pub fn is_in_p<N: IntoT<us>>(&self, p: Pt<N>) -> bool { self.is_in_t(p.tuple()) }
pub fn is_in_t<N: IntoT<us>>(&self, t: (N, N)) -> bool { t.0.into_t() < self.h && t.1.into_t() < self.w }
}
impl<T: Clone + Default> GridV<T> {
pub fn new(h: us, w: us) -> Self {
Self { g: vec![T::default(); h * w], h, w, }
}
}
impl ToString for GridV<char> {
fn to_string(&self) -> String {
let mut ret = "".to_owned();
for i in 0..self.h {
ret.push_str(format!("{}: ", i%10).as_str()); // line number
ret.push_str(self[i].str().as_str());
ret.push('\n');
}
ret
}
}
impl<T, N: IntoT<us>> Index<N> for GridV<T> {
type Output = [T];
fn index(&self, i: N) -> &Self::Output {
let idx = i.into_t() * self.w;
&self.g[idx..idx+self.w]
}
}
impl<T, N: IntoT<us>> IndexMut<N> for GridV<T> {
fn index_mut(&mut self, i: N) -> &mut Self::Output {
let idx = i.into_t() * self.w;
&mut self.g[idx..idx+self.w]
}
}
impl<T, N: IntoT<us>> Index<(N,N)> for GridV<T> {
type Output = T;
fn index(&self, index: (N,N)) -> &Self::Output { &self[index.0.into_t()][index.1.into_t()] }
}
impl<T, N: IntoT<us>> IndexMut<(N,N)> for GridV<T> {
fn index_mut(&mut self, index: (N,N)) -> &mut Self::Output { &mut self[index.0.into_t()][index.1.into_t()] }
}
impl<T, N: IntoT<us>> Index<Pt<N>> for GridV<T> {
type Output = T;
fn index(&self, p: Pt<N>) -> &Self::Output { &self[p.tuple()] }
}
impl<T, N: IntoT<us>> IndexMut<Pt<N>> for GridV<T> {
fn index_mut(&mut self, p: Pt<N>) -> &mut Self::Output { &mut self[p.tuple()] }
}
impl<T: Clone> From<&Vec<Vec<T>>> for GridV<T> {
fn from(value: &Vec<Vec<T>>) -> Self {
let (h, w) = (value.len(), value[0].len());
GridV{ g: value.iter().cloned().flatten().cv(), h, w }
}
}
pub struct ShortestPath {
pub start: Pt<us>,
pub dist: GridV<i64>,
pub prev: GridV<Pt<us>>,
}
impl ShortestPath {
pub fn restore_shortest_path(&self, mut t: Pt<us>) -> Vec<Pt<us>> {
let mut ps = vec![];
while t != Pt::<us>::INF { ps.push(t); t = self.prev[t]; }
ps.reverse();
assert!(ps[0] == self.start);
ps
}
}
impl GridV<char> {
// まだあまり動かしてないので、そのうちテスト必要
pub fn bfs(&self, s: Pt<us>) -> ShortestPath {
let mut que = deque::new();
let mut ret = ShortestPath {
start: s,
dist: GridV::with_default(self.h, self.w, i64::INF),
prev: GridV::with_default(self.h, self.w, Pt::<us>::INF),
};
que.push_back(s);
ret.dist[s] = 0;
while let Some(v) = que.pop_front() {
for d in Dir::VAL4 {
let nv = v.next(d);
if self.is_in_p(nv) && self[nv]!='#' && ret.dist[nv]==i64::INF {
ret.dist[nv] = ret.dist[v]+1;
ret.prev[nv] = v;
que.push_back(nv);
}
}
}
ret
}
}
pub trait CellTrait {
fn cost(&self, d: Dir) -> Option<i64>;
}
impl<T: CellTrait> GridV<T> {
pub fn dijkstra(&self, s: Pt<us>) -> ShortestPath {
type P = Pt<us>;
let mut ret = ShortestPath {
start: s,
dist: GridV::with_default(self.h,self.w,i64::INF),
prev: GridV::with_default(self.h,self.w,P::INF),
};
let mut q = bheap::new();
q.push(Reverse((0,s)));
ret.dist[s] = 0;
while let Some(Reverse((cost, v))) = q.pop() {
if ret.dist[v] < cost { continue; }
for d in Dir::VAL4 {
let Some(c) = self[v].cost(d) else { continue; };
let nv = v.next(d);
let nc = cost + c;
if chmin!(ret.dist[nv], nc) {
q.push(Reverse((nc, nv)));
ret.prev[nv] = v;
}
}
}
ret
}
}
}
pub mod pt {
#![allow(dead_code)]
use std::{*, ops::*, iter::Sum};
use crate::common::*;
use crate::{enrich_enum, count};
// Pt
#[derive(Copy,Clone,PartialEq,Eq,PartialOrd,Ord,Hash,Default)]
pub struct Pt<N> { pub x: N, pub y: N }
impl<N:fmt::Display> fmt::Debug for Pt<N> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "({},{})", self.x, self.y)
}
}
impl<N> Pt<N> {
pub fn new(x: impl IntoT<N>, y: impl IntoT<N>) -> Self { Pt{x:x.into_t(), y:y.into_t()} }
pub fn of(x: N, y: N) -> Pt<N> { Pt{x:x, y:y} }
pub fn tuple(self) -> (N, N) { (self.x, self.y) }
}
impl<N: SimplePrimInt> Pt<N> {
pub fn norm2(self) -> N { self.x * self.x + self.y * self.y }
pub fn on(self, h: Range<N>, w: Range<N>) -> bool { h.contains(&self.x) && w.contains(&self.y) }
pub fn manhattan_distance(self, p: Pt<N>) -> N { abs_diff(self.x, p.x) + abs_diff(self.y, p.y) }
}
impl<N: SimplePrimInt+FromT<i64>+ToF64> Pt<N> {
pub fn norm(self) -> f64 { self.norm2().f64().sqrt() }
}
impl<N: Wrapping> Wrapping for Pt<N> {
fn wrapping_add(self, a: Self) -> Self { Self::of(self.x.wrapping_add(a.x), self.y.wrapping_add(a.y)) }
}
impl Pt<us> {
pub fn wrapping_sub(self, a: Self) -> Self { Self::of(self.x.wrapping_sub(a.x), self.y.wrapping_sub(a.y)) }
pub fn wrapping_mul(self, a: Self) -> Self { Self::of(self.x.wrapping_mul(a.x), self.y.wrapping_mul(a.y)) }
pub fn next(self, d: Dir) -> Self { self.wrapping_add(d.p()) }
pub fn iter_next_4d(self) -> impl Iterator<Item=Self> { Dir::VAL4.iter().map(move|&d|self.next(d)) }
pub fn iter_next_8d(self) -> impl Iterator<Item=Self> { Dir::VALS.iter().map(move|&d|self.next(d)) }
pub fn prev(self, d: Dir) -> Self { self.wrapping_sub(d.p()) }
fn to_dir(a:Self, b:Self) -> Option<Dir> {
// aから見てbがどちらの方向にあるか
if a == b { return None; }
if a.x == b.x {
if a.y < b.y { Some(Dir::R) } else { Some(Dir::L) }
} else if a.y == b.y {
if a.x < b.x { Some(Dir::D) } else { Some(Dir::U) }
} else {
unreachable!("a and b are distant from each other. a={}, b={}", a, b);
}
}
pub fn to_dirs(rt:&Vec<Self>) -> Vec<Dir> {
(0..rt.len()-1).map(|i|(&rt[i],&rt[i+1]))
.map(|(&a,&b)|Dir::dir(a,b))
.cv()
}
pub fn move_xy(a:Self, b:Self) -> Vec<Self> {
// aからbに縦->横の順に進む
Self::move_impl(a, b, Self::new(b.x, a.y))
}
pub fn move_yx(a:Self, b:Self) -> Vec<Self> {
// aからbに横->縦の順に進む
Self::move_impl(a, b, Self::new(a.x, b.y))
}
fn move_impl(a:Self, b:Self, corner:Self) -> Vec<Self> {
let mut ret = vec![a];
let mut v = a;
for (x, y) in [(a, corner), (corner, b)] {
let Some(d) = Self::to_dir(x, y) else { continue };
for _ in 0..x.manhattan_distance(y) { v = v.next(d); ret.push(v); }
}
ret
}
}
impl<T: Inf> Inf for Pt<T> {
const INF: Self = Pt::<T>{x: T::INF, y: T::INF};
const MINF: Self = Pt::<T>{x: T::MINF, y: T::MINF};
}
pub type Radian = f64;
impl Pt<f64> {
pub fn rot(self, r: Radian) -> Pt<f64> {
let (x, y) = (self.x, self.y);
Self::new(r.cos()*x-r.sin()*y, r.sin()*x+r.cos()*y) // 反時計回りにr度回転(rはradian)
}
}
impl<N: SimplePrimInt+fmt::Display> fmt::Display for Pt<N> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{} {}", self.x, self.y) } }
impl<N: SimplePrimInt+fmt::Display> Fmt for Pt<N> { fn fmt(&self) -> String { format!("{} {}", self.x, self.y) } }
impl<N: AddAssign<N>+Copy> AddAssign<Pt<N>> for Pt<N> { fn add_assign(&mut self, rhs: Pt<N>) { self.x += rhs.x; self.y += rhs.y; } }
impl<N: SubAssign<N>+Copy> SubAssign<Pt<N>> for Pt<N> { fn sub_assign(&mut self, rhs: Pt<N>) { self.x -= rhs.x; self.y -= rhs.y; } }
impl<N: AddAssign<N>+Copy> AddAssign<N> for Pt<N> { fn add_assign(&mut self, rhs: N) { self.x += rhs; self.y += rhs; } }
impl<N: SubAssign<N>+Copy> SubAssign<N> for Pt<N> { fn sub_assign(&mut self, rhs: N) { self.x -= rhs; self.y -= rhs; } }
impl<N: MulAssign<N>+Copy> MulAssign<N> for Pt<N> { fn mul_assign(&mut self, rhs: N) { self.x *= rhs; self.y *= rhs; } }
impl<N: DivAssign<N>+Copy> DivAssign<N> for Pt<N> { fn div_assign(&mut self, rhs: N) { self.x /= rhs; self.y /= rhs; } }
impl<N: RemAssign<N>+Copy> RemAssign<N> for Pt<N> { fn rem_assign(&mut self, rhs: N) { self.x %= rhs; self.y %= rhs; } }
impl<N: AddAssign<N>+Copy> Add<Pt<N>> for Pt<N> { type Output = Pt<N>; fn add(mut self, rhs: Pt<N>) -> Self::Output { self += rhs; self } }
impl<N: SubAssign<N>+Copy> Sub<Pt<N>> for Pt<N> { type Output = Pt<N>; fn sub(mut self, rhs: Pt<N>) -> Self::Output { self -= rhs; self } }
impl<N: AddAssign<N>+Copy> Add<N> for Pt<N> { type Output = Pt<N>; fn add(mut self, rhs: N) -> Self::Output { self += rhs; self } }
impl<N: SubAssign<N>+Copy> Sub<N> for Pt<N> { type Output = Pt<N>; fn sub(mut self, rhs: N) -> Self::Output { self -= rhs; self } }
impl<N: MulAssign<N>+Copy> Mul<N> for Pt<N> { type Output = Pt<N>; fn mul(mut self, rhs: N) -> Self::Output { self *= rhs; self } }
impl<N: DivAssign<N>+Copy> Div<N> for Pt<N> { type Output = Pt<N>; fn div(mut self, rhs: N) -> Self::Output { self /= rhs; self } }
impl<N: RemAssign<N>+Copy> Rem<N> for Pt<N> { type Output = Pt<N>; fn rem(mut self, rhs: N) -> Self::Output { self %= rhs; self } }
impl<N: SimplePrimInt+FromT<is>> Neg for Pt<N> { type Output = Pt<N>; fn neg(mut self) -> Self::Output { self *= N::from_t(-1); self } }
impl<N: SimplePrimInt+Default> Sum for Pt<N> { fn sum<I: Iterator<Item=Self>>(iter: I) -> Self { iter.fold(Self::default(), |a, b| a + b) } }
impl<N: SimplePrimInt+FromT<is>+proconio::source::Readable<Output=N>+IntoT<N>> proconio::source::Readable for Pt<N> {
type Output = Pt<N>;
fn read<R: io::BufRead, S: proconio::source::Source<R>>(source: &mut S) -> Self::Output {
Pt::new(N::read(source), N::read(source))
}
}
impl<T> From<(T, T)> for Pt<T> {
fn from(t: (T, T)) -> Self { Self::of(t.0, t.1) }
}
enrich_enum! {
pub enum Dir {
R, L, D, U, RU, RD, LD, LU,
}
}
impl Dir {
pub const C4: [char; 4] = ['R', 'L', 'D', 'U'];
pub const VAL4: [Self; 4] = [Self::R,Self::L,Self::D,Self::U];
pub const P8: [Pt<us>; 8] = [
Pt::<us>{x:0,y:1},Pt::<us>{x:0,y:!0},Pt::<us>{x:1,y:0},Pt::<us>{x:!0,y:0},
Pt::<us>{x:1,y:1},Pt::<us>{x:1,y:!0},Pt::<us>{x:!0,y:1},Pt::<us>{x:!0,y:!0},
];
pub const REV8: [Self; 8] = [
Self::L,Self::R,Self::U,Self::D,
Self::LD,Self::LU,Self::RU,Self::RD,
];
pub const RROT90: [Self; 4] = [Self::D,Self::U,Self::L,Self::R];
pub const LROT90: [Self; 4] = [Self::U,Self::D,Self::R,Self::L];
pub const RROT45: [Self; 8] = [
Self::RD,Self::LU,Self::LD,Self::RU,
Self::R,Self::D,Self::L,Self::U,
];
pub const LROT45: [Self; 8] = [
Self::RU,Self::LD,Self::RD,Self::LU,
Self::U,Self::R,Self::D,Self::L,
];
#[inline] pub const fn c(self) -> char { Self::C4[self.id()] }
#[inline] pub const fn p(self) -> Pt<us> { Self::P8[self.id()] }
#[inline] pub const fn rev(self) -> Self { Self::REV8[self.id()] }
#[inline] pub const fn rrot90(self) -> Self { Self::RROT90[self.id()] }
#[inline] pub const fn lrot90(self) -> Self { Self::LROT90[self.id()] }
#[inline] pub const fn rrot45(self) -> Self { Self::RROT45[self.id()] }
#[inline] pub const fn lrot45(self) -> Self { Self::LROT45[self.id()] }
#[inline] pub fn dir(a: Pt<us>, b: Pt<us>) -> Self { (b.wrapping_sub(a)).into() } // a -> b
}
impl From<Pt<us>> for Dir { fn from(value: Pt<us>) -> Self { Self::P8.pos(&value).unwrap().into() } }
impl From<char> for Dir { fn from(value: char) -> Self { Self::C4.pos(&value).unwrap().into() } }
}
pub mod enrich_enum {
#![allow(dead_code)]
#[macro_export]
macro_rules! count {
() => (0usize);
( $x:tt $($xs:tt)* ) => (1usize + count!($($xs)*));
}
#[macro_export]
macro_rules! enrich_enum {
($(#[$meta:meta])* $vis:vis enum $name:ident { $($e:ident,)* }) => {
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, hash::Hash)]
$(#[$meta])*
$vis enum $name {
$($e,)*
}
impl $name {
pub const VALS: [Self; count!($($e)*)] = [$(Self::$e,)*];
#[inline] pub const fn id(self) -> us { self as us }
#[inline] pub const fn b(self) -> u32 { 1<<self.id() }
#[inline] pub const fn is_or(self, b: u32) -> bool { self.b() & b > 0 }
#[inline] pub const fn from_id(id: us) -> Self { Self::VALS[id] }
#[inline] pub const fn from_bit(b: u32) -> Self {
assert!(b.count_ones() <= 1);
Self::from_id(b.trailing_zeros() as usize + 1)
}
}
impl BitOr for $name {
type Output = u32;
fn bitor(self, rhs: Self) -> Self::Output { self.b() | rhs.b() }
}
impl From<us> for $name { fn from(value: us) -> Self { Self::from_id(value) } }
impl From<u32> for $name { fn from(value: u32) -> Self { Self::from_bit(value) } }
};
}
}
}
pub mod common {
#![allow(dead_code, unused_imports, unused_macros, non_snake_case, non_camel_case_types)]
use std::{*, ops::*, collections::*, iter::{Sum, FromIterator}};
pub type us = usize;
pub type is = isize;
pub type us1 = proconio::marker::Usize1;
pub type is1 = proconio::marker::Isize1;
pub type chars = proconio::marker::Chars;
pub type bytes = proconio::marker::Bytes;
pub type Str = String;
pub type map<K,V> = HashMap<K,V>;
pub type bmap<K,V> = BTreeMap<K,V>;
pub type set<V> = HashSet<V>;
pub type bset<V> = BTreeSet<V>;
pub type bheap<V> = BinaryHeap<V>;
pub type deque<V> = VecDeque<V>;
pub trait FromT<T> { fn from_t(t: T) -> Self; }
pub trait IntoT<T> { fn into_t(self) -> T; }
// PrimNum
pub trait SimplePrimInt:
Copy
+ PartialOrd<Self>
+ Add<Output=Self>
+ Sub<Output=Self>
+ Mul<Output=Self>
+ Div<Output=Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ Default
+ PartialEq
{
}
pub trait ExPrimInt: SimplePrimInt
+ Rem<Output=Self>
+ RemAssign
+ FromT<us>
{}
#[macro_export] macro_rules! impl_prim_num {
($($t:ty),*) => {$(
impl SimplePrimInt for $t { }
impl ExPrimInt for $t { }
impl FromT<us> for $t { fn from_t(n: us) -> Self { n as $t } }
impl FromT<is> for $t { fn from_t(n: is) -> Self { n as $t } }
impl IntoT<us> for $t { fn into_t(self) -> us { self as us } }
impl IntoT<is> for $t { fn into_t(self) -> is { self as is } }
impl IntoT<f64> for $t { fn into_t(self) -> f64 { self as f64 } }
impl IntoT<u8> for $t { fn into_t(self) -> u8 { self as u8 } }
impl IntoT<u32> for $t { fn into_t(self) -> u32 { self as u32 } }
impl IntoT<u64> for $t { fn into_t(self) -> u64 { self as u64 } }
impl IntoT<i32> for $t { fn into_t(self) -> i32 { self as i32 } }
impl IntoT<i64> for $t { fn into_t(self) -> i64 { self as i64 } }
impl IntoT<char> for $t { fn into_t(self) -> char { (self as u8) as char } }
)*}
}
impl_prim_num! {isize, i8, i32, i64, usize, u8, u32, u64, f32, f64}
pub trait ToUs { fn us(self) -> us; }
pub trait ToIs { fn is(self) -> is; }
pub trait ToI64 { fn i64(self) -> i64; }
pub trait ToF64 { fn f64(self) -> f64; }
pub trait ToU8 { fn u8(self) -> u8; }
pub trait ToU32 { fn u32(self) -> u32; }
pub trait ToI32 { fn i32(self) -> i32; }
pub trait ToChar { fn char(self) -> char; }
impl<T: IntoT<us>> ToUs for T { fn us(self) -> us { self.into_t() } }
impl<T: IntoT<is>> ToIs for T { fn is(self) -> is { self.into_t() } }
impl<T: IntoT<i64>> ToI64 for T { fn i64(self) -> i64 { self.into_t() } }
impl<T: IntoT<f64>> ToF64 for T { fn f64(self) -> f64 { self.into_t() } }
impl<T: IntoT<u8>> ToU8 for T { fn u8(self) -> u8 { self.into_t() } }
impl<T: IntoT<u32>> ToU32 for T { fn u32(self) -> u32 { self.into_t() } }
impl<T: IntoT<i32>> ToI32 for T { fn i32(self) -> i32 { self.into_t() } }
impl<T: IntoT<char>> ToChar for T { fn char(self) -> char { self.into_t() } }
impl IntoT<us> for char { fn into_t(self) -> us { self as us } }
impl IntoT<is> for char { fn into_t(self) -> is { self as is } }
impl IntoT<u8> for char { fn into_t(self) -> u8 { self as u8 } }
impl IntoT<u32> for char { fn into_t(self) -> u32 { self as u32 } }
impl IntoT<i32> for char { fn into_t(self) -> i32 { self as i32 } }
impl IntoT<u64> for char { fn into_t(self) -> u64 { self as u64 } }
impl IntoT<i64> for char { fn into_t(self) -> i64 { self as i64 } }
impl IntoT<char> for char { fn into_t(self) -> char { self } }
impl IntoT<char> for &char { fn into_t(self) -> char { *self } }
pub trait Inf {
const INF: Self;
const MINF: Self;
}
impl Inf for us {
const INF: Self = std::usize::MAX / 4;
const MINF: Self = 0;
}
impl Inf for is {
const INF: Self = std::isize::MAX / 4;
const MINF: Self = -Self::INF;
}
impl Inf for i64 {
const INF: Self = std::i64::MAX / 4;
const MINF: Self = -Self::INF;
}
pub trait Wrapping {
fn wrapping_add(self, a: Self) -> Self;
}
impl Wrapping for us { fn wrapping_add(self, a: Self) -> Self { self.wrapping_add(a) } }
impl Wrapping for is { fn wrapping_add(self, a: Self) -> Self { self.wrapping_add(a) } }
impl Wrapping for i64 { fn wrapping_add(self, a: Self) -> Self { self.wrapping_add(a) } }
// Utilities
#[macro_export] macro_rules! or { ($cond:expr;$a:expr,$b:expr) => { if $cond { $a } else { $b } }; }
#[macro_export] macro_rules! chmax { ($a:expr,$b:expr) => { { let v = $b; if $a < v { $a = v; true } else { false } } } }
#[macro_export] macro_rules! chmin { ($a:expr,$b:expr) => { { let v = $b; if $a > v { $a = v; true } else { false } } } }
#[macro_export] macro_rules! add { ($a:expr,$b:expr) => { { let v = $b; $a += v; } } }
#[macro_export] macro_rules! sub { ($a:expr,$b:expr) => { { let v = $b; $a -= v; } } }
#[macro_export] macro_rules! mul { ($a:expr,$b:expr) => { { let v = $b; $a *= v; } } }
#[macro_export] macro_rules! div { ($a:expr,$b:expr) => { { let v = $b; $a /= v; } } }
#[macro_export] macro_rules! rem { ($a:expr,$b:expr) => { { let v = $b; $a %= v; } } }
pub fn abs_diff<T:PartialOrd+Sub<Output=T>>(n1: T, n2: T) -> T { if n1 >= n2 { n1 - n2 } else { n2 - n1 } }
pub fn floor<N: SimplePrimInt>(a: N, b: N) -> N { a / b }
pub fn asc <T:Ord>(a: &T, b: &T) -> cmp::Ordering { a.cmp(b) }
pub fn desc<T:Ord>(a: &T, b: &T) -> cmp::Ordering { b.cmp(a) }
pub fn min_max<T: Ord+Copy>(a: T, b: T) -> (T, T) { (cmp::min(a,b), cmp::max(a,b)) }
pub trait IterTrait : Iterator {
fn grouping_to_bmap<'a, K:Ord+Clone, V>(&'a mut self, get_key: impl Fn(&Self::Item)->K, get_val: impl Fn(&Self::Item)->V) -> bmap<K, Vec<V>> {
self.fold(bmap::<_,_>::new(), |mut m, x| { m.entry(get_key(&x)).or_default().push(get_val(&x)); m })
}
fn grouping_to_map<K:Eq+hash::Hash+Clone, V>(&mut self, get_key: impl Fn(&Self::Item)->K, get_val: impl Fn(&Self::Item)->V) -> map<K, Vec<V>> {
self.fold(map::<_,_>::new(), |mut m, x| { m.entry(get_key(&x)).or_default().push(get_val(&x)); m })
}
fn cv(&mut self) -> Vec<Self::Item> { self.collect::<Vec<_>>() }
}
pub trait CharIterTrait<T: IntoT<char>> : Iterator<Item=T> {
fn cstr(&mut self) -> String { self.map(|c|c.into_t()).collect::<Str>() }
}
pub trait HashIterTrait : Iterator where Self::Item: Eq+hash::Hash {
fn cset(&mut self) -> set<Self::Item> { self.collect::<set<_>>() }
}
pub trait OrdIterTrait : Iterator where Self::Item: Ord {
fn cbset(&mut self) -> bset<Self::Item> { self.collect::<bset<_>>() }
}
pub trait PairHashIterTrait<T, U> : Iterator<Item=(T,U)> where T: Eq+hash::Hash {
fn cmap(&mut self) -> map<T, U> { self.collect::<map<_,_>>() }
}
pub trait PairOrdIterTrait<T, U> : Iterator<Item=(T,U)> where T: Ord {
fn cbmap(&mut self) -> bmap<T, U> { self.collect::<bmap<_,_>>() }
}
impl<I> IterTrait for I where I: Iterator { }
impl<I, T: IntoT<char>> CharIterTrait<T> for I where I: Iterator<Item=T> { }
impl<I> HashIterTrait for I where I: Iterator, Self::Item: Eq+hash::Hash { }
impl<I> OrdIterTrait for I where I: Iterator, Self::Item: Ord { }
impl<I, T, U> PairHashIterTrait<T, U> for I where I: Iterator<Item=(T,U)>, T: Eq+hash::Hash { }
impl<I, T, U> PairOrdIterTrait<T, U> for I where I: Iterator<Item=(T,U)>, T: Ord { }
// Vec
pub trait VecCount<T> { fn count(&self, f: impl FnMut(&T)->bool) -> us; }
impl<T> VecCount<T> for [T] { fn count(&self, mut f: impl FnMut(&T)->bool) -> us { self.iter().filter(|&x|f(x)).count() } }
pub trait VecMax<T> { fn vmax(&self) -> T; }
impl<T:Clone+Ord> VecMax<T> for [T] { fn vmax(&self) -> T { self.iter().cloned().max().unwrap() } }
pub trait VecMin<T> { fn vmin(&self) -> T; }
impl<T:Clone+Ord> VecMin<T> for [T] { fn vmin(&self) -> T { self.iter().cloned().min().unwrap() } }
pub trait VecSum<T> { fn sum(&self) -> T; }
impl<T:Clone+Sum<T>> VecSum<T> for [T] { fn sum(&self) -> T { self.iter().cloned().sum::<T>() } }
pub trait VecStr<T> { fn str(&self) -> Str; }
impl<T:ToString> VecStr<T> for [T] { fn str(&self) -> Str { self.iter().map(|x|x.to_string()).collect::<Str>() } }
pub trait VecMap<T> { fn map<U>(&self, f: impl FnMut(&T)->U) -> Vec<U>; }
impl<T> VecMap<T> for [T] { fn map<U>(&self, mut f: impl FnMut(&T)->U) -> Vec<U> { self.iter().map(|x|f(x)).cv() } }
pub trait VecPos<T> { fn pos(&self, t: &T) -> Option<us>; }
impl<T:Eq> VecPos<T> for [T] { fn pos(&self, t: &T) -> Option<us> { self.iter().position(|x|x==t) } }
pub trait VecRpos<T> { fn rpos(&self, t: &T) -> Option<us>; }
impl<T:Eq> VecRpos<T> for [T] { fn rpos(&self, t: &T) -> Option<us> { self.iter().rposition(|x|x==t) } }
pub trait VecSet<T> { fn set(&mut self, i: us, t: T) -> T; }
impl<T> VecSet<T> for [T] { fn set(&mut self, i: us, mut t: T) -> T { std::mem::swap(&mut self[i], &mut t); t } }
// Deque
pub trait DequePush<T> { fn push(&mut self, t: T); }
impl<T> DequePush<T> for VecDeque<T> { fn push(&mut self, t: T) { self.push_back(t); } }
pub trait DequePop<T> { fn pop(&mut self) -> Option<T>; }
impl<T> DequePop<T> for VecDeque<T> { fn pop(&mut self) -> Option<T> { self.pop_back() } }
pub trait Identify {
type Ident;
fn ident(&self) -> Self::Ident;
fn ident_by(&self, s: &str) -> Self::Ident;
}
impl<T: IntoT<u8> + Copy> Identify for T {
type Ident = us;
fn ident(&self) -> us {
let c = self.into_t();
if b'0' <= c && c <= b'9' { (c - b'0').us() }
else if b'a' <= c && c <= b'z' { (c - b'a').us() }
else if b'A' <= c && c <= b'Z' { (c - b'A').us() }
else { 0 }
}
fn ident_by(&self, s: &str) -> us {
let b = self.into_t();
s.chars().position(|c|c==b.char()).expect("error")
}
}
impl<T: Identify> Identify for [T] {
type Ident = Vec<T::Ident>;
fn ident(&self) -> Self::Ident { self.iter().map(|x|x.ident()).cv() }
fn ident_by(&self, s: &str) -> Self::Ident { self.iter().map(|x|x.ident_by(s)).cv() }
}
impl Identify for &str {
type Ident = Vec<us>;
fn ident(&self) -> Self::Ident { self.as_bytes().ident() }
fn ident_by(&self, s: &str) -> Self::Ident { self.as_bytes().ident_by(s) }
}
impl Identify for String {
type Ident = Vec<us>;
fn ident(&self) -> Self::Ident { self.as_bytes().ident() }
fn ident_by(&self, s: &str) -> Self::Ident { self.as_bytes().ident_by(s) }
}
pub trait ToC: IntoT<u8> + Copy {
fn to_c_by(self, ini: char) -> char { (ini.u8() + self.u8()).char() }
}
impl<T: IntoT<u8>+Copy> ToC for T {}
trait Joiner { fn join(self, sep: &str) -> String; }
impl<It: Iterator<Item=String>> Joiner for It { fn join(self, sep: &str) -> String { self.collect::<Vec<_>>().join(sep) } }
pub trait Fmt { fn fmt(&self) -> String; }
macro_rules! fmt_primitive { ($($t:ty),*) => { $(impl Fmt for $t { fn fmt(&self) -> String { self.to_string() }})* } }
fmt_primitive! {
u8, u16, u32, u64, u128, i8, i16, i32, i64, i128,
usize, isize, f32, f64, char, &str, String, bool
}
impl<T: Fmt> Fmt for [T] { fn fmt(&self) -> String { self.iter().map(|e| e.fmt()).join(" ") } }
impl<T: Fmt> Fmt for VecDeque<T> { fn fmt(&self) -> String { self.iter().map(|e| e.fmt()).join(" ") } }
impl<T: Fmt> Fmt for set<T> { fn fmt(&self) -> String { self.iter().map(|e| e.fmt()).join(" ") } }
impl<T: Fmt> Fmt for bset<T> { fn fmt(&self) -> String { self.iter().map(|e| e.fmt()).join(" ") } }
#[macro_export] macro_rules! fmt {
($a:expr, $($b:expr),*) => {{ format!("{} {}", fmt!(($a)), fmt!($($b),*)) }};
($a:expr) => {{ ($a).fmt() }};
(@debug $a:expr, $($b:expr),*) => {{ format!("{} {}", fmt!(@debug ($a)), fmt!(@debug $($b),*)) }};
(@debug $a:expr) => {{ format!("{:?}", ($a)) }};
}
#[macro_export] macro_rules! vprintln {
($a:expr) => { for x in &($a) { println!("{}", x); } };
}
#[macro_export] macro_rules! vprintsp {
($a:expr) => {
{
use itertools::Itertools;
println!("{}", ($a).iter().join(" "));
}
}
}
#[macro_export] macro_rules! print_grid {
($a:expr) => { for v in &($a) { println!("{}", v.iter().collect::<Str>()); } };
}
pub fn yes(b: bool) -> &'static str { if b { "yes" } else { "no" } }
pub fn Yes(b: bool) -> &'static str { if b { "Yes" } else { "No" } }
pub fn YES(b: bool) -> &'static str { if b { "YES" } else { "NO" } }
pub fn no(b: bool) -> &'static str { yes(!b) }
pub fn No(b: bool) -> &'static str { Yes(!b) }
pub fn NO(b: bool) -> &'static str { YES(!b) }
}