結果
| 問題 |
No.2615 ペアの作り方
|
| ユーザー |
 vjudge1
|
| 提出日時 | 2025-07-16 01:03:37 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 19 ms / 2,000 ms |
| コード長 | 24,025 bytes |
| コンパイル時間 | 14,132 ms |
| コンパイル使用メモリ | 400,552 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-16 01:03:53 |
| 合計ジャッジ時間 | 14,886 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 |
ソースコード
#![allow(unused_must_use, non_snake_case, unused_labels, unused_imports)]
use external::*;
use cplib::prelude::*;
use nest as vec;
const INTERACTIVE: bool = false;
// const INTERACTIVE: bool = true; use input_interactive as input;
fn solve() {
input! {
N: usize, mut X: [u64; N], mut Y: [u64; N]
}
let MOD = 998244353;
X.sort(); Y.sort_by_key(|v| !v);
let mut cnt = 0;
for i in (0..N).rev() {
if X[i] > Y[i] {
cnt += 1;
} else {
break;
}
}
let mut tmp = 1;
for i in 2..=cnt {
tmp = tmp * i % MOD;
}
let mut tmp2 = 1;
for i in 2..=N-cnt {
tmp2 = tmp2 * i % MOD;
}
out << (tmp*tmp2 % MOD);
}
fn main() { Output::init(INTERACTIVE || !SUBMISSION); solve(); Output::print() }
// You can view my cp-library at https://github.com/solalyth/cplib-rs
mod cplib { #![allow(unused_macros, dead_code)] pub const SUBMISSION: bool = true; pub mod prelude { pub use std::{ collections::{VecDeque, HashMap, HashSet, BTreeMap, BTreeSet, BinaryHeap}, cmp::{Ordering, Reverse}, mem::{swap, replace} }; pub use crate::cplib::{ *, SUBMISSION, ds::segtree::SegtreeOp, util::{ output::{Output, out, end}, traits::*, func::binary_search }, }; } pub mod ds { pub mod unionfind { pub use crate::cplib::abstracts::{Group, Nop}; use crate::cplib::util::func::join; pub struct UnionFind<Op: Group> { par: Vec<usize>, size: Vec<usize>, diff: Vec<Op::T>, next: Vec<usize> } impl UnionFind<Nop> { pub fn new_nop(len: usize) -> Self { Self::new(len) } } impl<Op: Group> UnionFind<Op> { pub fn new(len: usize) -> Self { UnionFind { par: (0..len).collect(), size: vec![1; len], diff: vec![Op::e(); len], next: (0..len).collect() } } pub fn extend(&mut self, len: usize) { let bef = self.len(); self.par.extend(bef..len); self.size.resize(len, 1); self.diff.resize(len, Op::e()); self.next.extend(bef..len); } pub fn len(&self) -> usize { self.par.len() } pub fn leader(&mut self, i: usize) -> usize { let p = self.par[i]; if self.par[p] == p { return p; } let u = self.leader(p); self.diff[i] = Op::add(&self.diff[i], &self.diff[p]); self.par[i] = u; u } pub fn size(&mut self, mut i: usize) -> usize { i = self.leader(i); self.size[i] } pub fn is_same(&mut self, i: usize, j: usize) -> bool { self.leader(i) == self.leader(j) } pub fn diff(&mut self, i: usize, j: usize) -> Op::T { assert!(self.is_same(i, j)); Op::sub(&self.diff[i], &self.diff[j]) } pub fn merge(&mut self, i: usize, j: usize, mut w: Op::T) -> Option<(usize, usize)> { let (mut u, mut v) = (self.leader(i), self.leader(j)); w = Op::sub(&Op::add(&w, &self.diff[j]), &self.diff[i]); if u == v { return if w == Op::e() { Some((u, u)) } else { None } } if !(self.size[u] < self.size[v]) { (u, v) = (v, u); w = Op::inv(&w); } self.par[u] = v; self.diff[u] = w; self.size[v] += self.size[u]; self.next.swap(i, j); Some((v, u)) } pub fn groups(&mut self) -> Vec<Vec<usize>> { let mut res = crate::nest![void; self.len()]; for i in 0..self.len() { res[self.leader(i)].push(i); } res.retain(|v| v.len() != 0); res } pub fn group(&self, i: usize) -> Vec<usize> { let (mut res, mut j) = (vec![i], self.next[i]); while j != i { res.push(j); j = self.next[j]; } res } pub fn leaders(&self) -> Vec<usize> { (0..self.len()).filter(|&i| self.par[i] == i).collect() } } impl<Op: Group> Clone for UnionFind<Op> { fn clone(&self) -> Self { Self { par: self.par.clone(), size: self.size.clone(), diff: self.diff.clone(), next: self.next.clone() } } } impl<Op: Group> std::fmt::Debug for UnionFind<Op> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut uf = self.clone(); let g = uf.groups().into_iter().map(|s| { join(s.into_iter().map(|i| format!("{i}({:?})", uf.diff[i]).trim_end_matches("(())").into())).unwrap() }); write!(f, "[{}]", join(g.into_iter().map(|s| format!("{{{s}}}"))).unwrap_or(String::new())) } } } pub mod segtree { use std::{fmt::Debug, mem::replace, ops::{Index, IndexMut, RangeBounds}, slice::SliceIndex}; use crate::cplib::util::func::to_bounds; #[allow(unused_variables)] pub trait SegtreeOp: Sized { type Value: Clone + PartialEq + Debug; type Lazy: Clone; fn id_value() -> Self::Value; fn prod_value(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; fn act_value(value: &mut Self::Value, lazy: &Self::Lazy) {} fn prod_lazy(lazy: &mut Self::Lazy, ad: &Self::Lazy) {} fn segtree_new(len: usize) -> Segtree<Self> { Segtree::new(len) } fn segtree_from_iter(iter: impl Iterator<Item = Self::Value>) -> Segtree<Self> { Segtree::from_iter(iter) } } pub struct Segtree<Op: SegtreeOp> { tree: Vec<Op::Value>, lazy: Vec<Option<Op::Lazy>>, depth: u32 } impl<Op: SegtreeOp> Segtree<Op> { pub fn new(len: usize) -> Self { let depth = (len.max(2)-1).ilog2() + 2; Segtree { tree: vec![Op::id_value(); 1<<depth], lazy: vec![None; 1<<depth], depth } } pub fn len(&self) -> usize { 1 << self.depth-1 } pub fn get(&mut self, mut i: usize) -> &Op::Value { i += self.len(); for j in (1..self.depth).rev() { self.push(i >> j); } &self.tree[i] } pub fn set(&mut self, mut i: usize, f: impl FnOnce(&Op::Value) -> Op::Value) { i += self.len(); for j in (1..self.depth).rev() { self.push(i >> j); } let new = f(&self.tree[i]); if new != self.tree[i] { self.tree[i] = new; for j in 1..self.depth { self.update(i >> j); } } } pub fn entry(&mut self) -> Entry<'_, Op> { for i in 1..self.len() { self.push(i); } Entry { seg: self, changed: false } } pub fn fold(&mut self, range: impl RangeBounds<usize>) -> Op::Value { let [mut l, mut r] = to_bounds(range, self.len()).map(|v| v+self.len()); if r == self.len() { return Op::id_value(); } let (mut rl, mut rr) = (Op::id_value(), Op::id_value()); for i in (1..self.depth).rev() { self.push(l >> i); self.push(r-1 >> i); } while l < r { if l&1 == 1 { rl = Op::prod_value(&rl, &self.tree[l]); l += 1; } if r&1 == 1 { rr = Op::prod_value(&self.tree[r-1], &rr); } l >>= 1; r >>= 1; } Op::prod_value(&rl, &rr) } pub fn apply_lazy(&mut self, range: impl RangeBounds<usize>, lazy: Op::Lazy) { let [l, r] = to_bounds(range, self.len()).map(|v| v + self.len()); if r == self.len() { return; } for i in (1..self.depth).rev() { self.push(l >> i); self.push(r-1 >> i); } let (mut s, mut t) = (l, r); while s < t { if s&1 == 1 { Op::act_value(&mut self.tree[s], &lazy); self.comp_lazy(s, &lazy); s += 1; } if t&1 == 1 { t -= 1; Op::act_value(&mut self.tree[t], &lazy); self.comp_lazy(t, &lazy); } s >>= 1; t >>= 1; } for i in 1..self.depth { if ((l >> i) << i) != l { self.update(l >> i); } if ((r >> i) << i) != r { self.update(r-1 >> i); } } } pub fn max_right(&mut self, l: usize, f: impl Fn(&Op::Value) -> bool) -> usize { assert!(l <= self.len()); if l == self.len() { return self.len(); } let (mut r, mut val) = (l + self.len(), Op::id_value()); for i in (1..self.depth).rev() { self.push(r >> i); } loop { while r&1 == 0 { r >>= 1; } let tmp = Op::prod_value(&val, &self.tree[r]); if !f(&tmp) { break; } val = tmp; r += 1; if r & r-1 == 0 { return self.len(); } } while r < self.len() { self.push(r); r *= 2; let tmp = Op::prod_value(&val, &self.tree[r]); if f(&tmp) { val = tmp; r += 1; } } r - self.len() } pub fn min_left(&mut self, r: usize, f: impl Fn(&Op::Value) -> bool) -> usize { assert!(r <= self.len()); if r == 0 { return 0; } let (mut l, mut val) = (r + self.len(), Op::id_value()); for i in (1..self.depth).rev() { self.push(l-1 >> i); } loop { l -= 1; while l != 1 && l&1 == 1 { l >>= 1; } let tmp = Op::prod_value(&self.tree[l], &val); crate::epr!("{tmp:?}"); if !f(&tmp) { break; } val = tmp; if l & l-1 == 0 { return 0; } } while l < self.len() { self.push(l); l = 2*l + 1; let tmp = Op::prod_value(&self.tree[l], &val); if f(&tmp) { val = tmp; l -= 1; } } l+1 - self.len() } #[track_caller] fn push(&mut self, i: usize) { debug_assert!(i != 0); debug_assert!(i < self.len()); let Some(lazy) = replace(&mut self.lazy[i], None) else { return }; Op::act_value(&mut self.tree[2*i], &lazy); Op::act_value(&mut self.tree[2*i+1], &lazy); self.comp_lazy(2*i, &lazy); self.comp_lazy(2*i+1, &lazy); } fn update(&mut self, i: usize) { debug_assert!(i < self.len()); debug_assert!(self.lazy[i].is_none()); self.tree[i] = Op::prod_value(&self.tree[2*i], &self.tree[2*i+1]); } fn comp_lazy(&mut self, i: usize, ad: &Op::Lazy) { if let Some(lazy) = &mut self.lazy[i] { Op::prod_lazy(lazy, ad); } else { self.lazy[i] = Some(ad.clone()); } } } impl<Op: SegtreeOp> Clone for Segtree<Op> { fn clone(&self) -> Self { Self { tree: self.tree.clone(), lazy: self.lazy.clone(), depth: self.depth.clone() } } } impl<Op: SegtreeOp> Debug for Segtree<Op> where Op::Value: Debug { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut seg = self.clone(); for i in 1..seg.len() { seg.push(i); } write!(f, "{:?}", &seg.tree[self.len()..]) } } impl<Op: SegtreeOp> FromIterator<Op::Value> for Segtree<Op> { fn from_iter<T: IntoIterator<Item = Op::Value>>(iter: T) -> Self { let v = iter.into_iter().collect::<Vec<_>>(); let mut seg = Self::new(v.len()); let len = seg.len(); for (i, v) in v.into_iter().enumerate() { seg.tree[len+i] = v; } for i in (1..seg.len()).rev() { seg.update(i); } seg } } pub struct Entry<'a, Op: SegtreeOp> { seg: &'a mut Segtree<Op>, changed: bool } impl<Op: SegtreeOp, I: SliceIndex<[Op::Value]>> Index<I> for Entry<'_, Op> { type Output = I::Output; fn index(&self, index: I) -> &Self::Output { Index::index(&self.seg.tree[self.seg.len()..], index) } } impl<Op: SegtreeOp, I: SliceIndex<[Op::Value]>> IndexMut<I> for Entry<'_, Op> { fn index_mut(&mut self, index: I) -> &mut Self::Output { let len = self.seg.len(); self.changed = true; IndexMut::index_mut(&mut self.seg.tree[len..], index) } } impl<Op: SegtreeOp> Drop for Entry<'_, Op> { fn drop(&mut self) { if self.changed { for i in (1..self.seg.len()).rev() { self.seg.update(i); } } } } } } pub mod algo { } pub mod graph { } pub mod abstracts { use std::fmt::Debug; pub struct Nop; pub trait Monoid: Sized { type T: Clone + PartialEq + Debug; fn e() -> Self::T; fn prod(l: &Self::T, r: &Self::T) -> Self::T; } pub trait Group { type T: Clone + PartialEq + Debug; fn e() -> Self::T; fn add(l: &Self::T, r: &Self::T) -> Self::T; fn inv(x: &Self::T) -> Self::T; fn sub(l: &Self::T, r: &Self::T) -> Self::T { Self::add(l, &Self::inv(r)) } } impl Group for Nop { type T = (); fn e() {} fn add(_: &(), _: &()) {} fn inv(_: &()) {} } } pub mod math { pub mod func { pub fn gcd(mut a: i64, mut b: i64) -> i64 { while b != 0 { (a, b) = (b, a%b); } a.abs() } pub fn extended_gcd(mut a: i64, mut b: i64) -> (i64, i64, i64) { let mut st = vec![]; while b != 0 { st.push(a/b); (a, b) = (b, a%b); } let (mut x, mut y) = (a.signum(), 0); for z in st.into_iter().rev() { (x, y) = (y, x - z*y); } (x, y, a.abs()) } pub fn mpow(mut x: usize, mut n: usize, m: usize) -> usize { x %= m; if x == 0 { return 0; } let mut res = 1; while n != 0 { if n&1 == 1 { res = res*x % m; } x = x*x % m; n >>= 1; } res } pub fn solve_quad(mut a: i128, mut b: i128, mut c: i128) -> Option<Vec<i128>> { fn isqrt(n: i128) -> i128 { (n as f64).sqrt() as i128 } let mut res = vec![]; if a == 0 { if b == 0 && c == 0 { return None; } if b != 0 && c%b == 0 { res.push(-c/b); } return Some(res); } if a < 0 { (a, b, c) = (-a, -b, -c); } let d2 = b*b - 4*a*c; if d2 < 0 || isqrt(d2).pow(2) != d2 { return Some(res); } let d = isqrt(d2); if (-b-d) % (2*a) == 0 { res.push((-b-d)/(2*a)); } if (-b+d) % (2*a) == 0 { res.push((-b+d)/(2*a)); } Some(res) } pub fn quotient_floor(n: usize) -> Vec<(usize, usize, usize)> { let mut res = vec![]; let mut i = 1; while i*i <= n { res.push((i, i, n/i)); i += 1; } for j in (1..=n/i).rev() { if n/j - n/(j+1) != 0 { res.push((n/(j+1)+1, n/j, j)); } } res } pub fn quotient_ceil(n: usize) -> Vec<(usize, usize, usize)> { let mut res = vec![]; let mut i = 1; while (i+1)*(i+1) <= n { res.push((i, i, (n+i-1)/i)); i += 1; } for j in (2..=(n+i-1)/i).rev() { let l = (n+j-1)/j; let r = (n-1)/(j-1); assert!((n+l-1)/l == j && (n+r-1)/r == j); res.push(((n+j-1)/j, (n-1)/(j-1), j)); } res.push((n, n, 1)); res } } pub mod prime { use std::ops::{Add, Sub}; const MASK_29BIT: usize = (1<<29)-1; pub struct LpfSieve { primes: Vec<usize>, table: Vec<usize>, } impl LpfSieve { pub fn new(mut max: usize) -> Self { assert!(usize::BITS == 64); max = max.max(10); let mut primes = vec![]; let mut table = vec![0; max+1]; for i in 2..=max { if table[i] == 0 { primes.push(i); table[i] = (1 << 58) + (i << 29) + 1; } let lpf_i = (table[i] >> 29) & MASK_29BIT; for &p in &primes { if !(p <= lpf_i && i*p <= max) { break; } table[p*i] = if p == lpf_i { table[i] + (1 << 58) } else { (1 << 58) + (p << 29) + i }; } } Self { primes, table } } pub fn max(&self) -> usize { self.table.len()-1 } pub fn primes(&self) -> &[usize] { &self.primes } pub fn is_prime(&self, n: usize) -> bool { (self.table[n] >> 29) & MASK_29BIT == n } pub fn data(&self, n: usize) -> (usize, usize, usize) { assert!(2 <= n); ((self.table[n] >> 29) & MASK_29BIT, self.table[n] >> 58, self.table[n] & MASK_29BIT) } pub fn fold<T>(&self, mut n: usize, mut init: T, mut f_vpe: impl FnMut(&mut T, usize, usize)) -> T { assert!(n != 0); while n != 1 { let (lpf, exp, nx) = self.data(n); f_vpe(&mut init, lpf, exp); n = nx; } init } pub fn factorize(&self, n: usize) -> Vec<(usize, usize)> { self.fold(n, vec![], |v, p, e| { v.push((p, e)); } ) } pub fn factorize_big(&self, mut n: usize) -> Vec<(usize, usize)> { assert_ne!(n, 0); let mut res = vec![]; for &p in &self.primes { let mut cnt = 0; while n%p == 0 { cnt += 1; n /= p; } if cnt != 0 { res.push((p, cnt)); } if n < p*p { break; } } if n != 1 { res.push((n, 1)); } res } pub fn divisors(&self, n: usize) -> Vec<usize> { assert!(n != 0); self.fold(n, vec![1], |v, p, e| { for i in 0..v.len() { let mut k = 1; for _ in 0..e { k *= p; v.push(v[i]*k); } } }) } pub fn totient_point(&self, n: usize) -> usize { self.fold(n, n, |v, p, _e| { *v -= *v/p; }) } pub fn totient(&self, n: usize) -> Vec<usize> { let mut res = vec![0; n+1]; res[1] = 1; for i in 2..=n { let (lpf, exp, _nx) = self.data(i); res[i] = res[i/lpf] * if exp == 1 { lpf-1 } else { lpf }; } res } pub fn mobius_point(&self, n: usize) -> i64 { self.fold(n, 1, |v, _p, e| { *v = if e == 1 { -*v } else { 0 }; }) } pub fn mobius(&self, n: usize) -> Vec<i64> { let mut res = vec![0; n+1]; res[1] = 1; for i in 2..=n { let (_lpf, exp, nx) = self.data(i); if exp == 1 { res[i] = -res[nx]; } } res } pub fn div_zeta<T: Copy + Add<Output = T>>(&self, mut f: Vec<T>) -> Vec<T> { let vl = f.len()-1; for &p in self.primes() { if vl < p { break; } for i in 1..=vl/p { f[i*p] = f[i*p] + f[i]; } } f } pub fn div_mobius<T: Copy + Sub<Output = T>>(&self, mut g: Vec<T>) -> Vec<T> { let vl = g.len()-1; for &p in self.primes() { if vl < p { break; } for i in (1..=vl/p).rev() { g[i*p] = g[i*p] - g[i]; } } g } pub fn div_mobius_point<T: Default + Copy + Add<Output = T> + Sub<Output = T>>(&self, g: &[T], idx: usize) -> T { let mut res = T::default(); for i in self.fold(idx, vec![1i32], |v, p, _| { for i in 0..v.len() { v.push(-v[i] * p as i32); } }) { if 0 <= i { res = res + g[idx/i as usize]; } else { res = res - g[idx/-i as usize]; } } res } pub fn mul_zeta<T: Copy + Add<Output = T>>(&self, mut f: Vec<T>) -> Vec<T> { let vl = f.len() - 1; for &p in self.primes() { if vl < p { break; } for i in (1..=vl/p).rev() { f[i] = f[i] + f[i*p]; } } f } pub fn mul_mobius<T: Copy + Sub<Output = T>>(&self, mut g: Vec<T>) -> Vec<T> { let vl = g.len() - 1; for &p in self.primes() { if vl < p { break; } for i in 1..=vl/p { g[i*p] = g[i*p] - g[i]; } } g } pub fn mul_mobius_point<T: Default + Copy + Add<Output = T> + Sub<Output = T>>(&self, g: &[T], idx: usize) -> T { let mut res = T::default(); let gl = g.len() - 1; let t = self.mobius(gl/idx); for (i, m) in t.into_iter().enumerate() { if m == 1 { res = res + g[i*idx]; } else if m == -1 { res = res - g[i*idx]; } } res } } } } pub mod util { pub mod output { #![allow(static_mut_refs)] use std::{mem::replace, ops::{Not, Shl}, fmt::Write}; static mut BUFFER: Buffer = Buffer { buf: String::new(), endp: false, prev: Previous::LineHead }; #[allow(non_upper_case_globals)] pub static out: Output = Output; pub struct Buffer { buf: String, endp: bool, prev: Previous, } impl Buffer { const LEN: usize = 16*1024*1024; fn print(&mut self) { if replace(&mut self.prev, Previous::LineHead) == Previous::LineHead { self.buf.pop(); } if self.buf.is_empty() { if !crate::cplib::SUBMISSION { println!("\x1b[32m>> (empty)\x1b[0m"); } return; } if crate::cplib::SUBMISSION { println!("{}", self.buf); } else { eprint!("\x1b[32m"); for s in self.buf.split('\n') { eprint!(">> "); println!("{s}"); } eprint!("\x1b[0m"); } self.buf.clear(); } fn space(&mut self, sp: bool) { let prev = replace(&mut self.prev, if sp {Previous::Space} else {Previous::NoSpace}); if (sp || prev == Previous::Space) && prev != Previous::LineHead { self.buf.push(' '); } } } #[derive(Clone, Copy)] pub struct Output<const SP: bool = true>; impl Output { pub fn init(endp: bool) { unsafe { BUFFER.buf.reserve(Buffer::LEN); BUFFER.endp = endp; } } pub fn print() { unsafe { BUFFER.print(); } } } impl<const SP: bool> Output<SP> { pub fn space() { unsafe { if BUFFER.prev == Previous::NoSpace { BUFFER.prev = Previous::Space; } } } fn push<T: Primitive>(v: &T) { unsafe { BUFFER.space(SP); v.fmt(&mut BUFFER.buf); } } } impl Not for Output { type Output = Output<false>; fn not(self) -> Self::Output { Output } } impl<const SP: bool, T: Primitive> Shl<T> for Output<SP> { type Output = Self; fn shl(self, rhs: T) -> Self::Output { Self::push(&rhs); self } } macro_rules! impl_for_slices { ($t:ty) => { impl<const SP: bool, T: Primitive> Shl<$t> for Output<SP> { type Output = Self; fn shl(self, rhs: $t) -> Self::Output { for v in rhs { Self::push(v); } self } } }; ($($t:ty),+) => { $(impl_for_slices!($t);)+ } } impl_for_slices!(&[T], &Vec<T>); impl<const SP: bool> Shl<end> for Output<SP> { type Output = Self; fn shl(self, _: end) -> Self::Output { unsafe { if BUFFER.endp { BUFFER.print(); } else { BUFFER.buf += "\n"; BUFFER.prev = Previous::LineHead; } } self } } #[allow(non_camel_case_types)] pub struct end; #[derive(PartialEq, Eq, Clone, Copy)] enum Previous { Space, NoSpace, LineHead, } trait Primitive { fn fmt(&self, buf: &mut String); } macro_rules! impl_primitive { ($t:ty) => { impl Primitive for $t { fn fmt(&self, buf: &mut String) { write!(buf, "{self}").ok(); } } }; ($($t:ty),+) => { $(impl_primitive!($t);)+ } } impl_primitive!(char, u32, u64, u128, usize, i32, i64, i128, f32, f64, &str, &String); impl Primitive for u8 { fn fmt(&self, buf: &mut String) { buf.push(*self as char); } } impl Primitive for bool { fn fmt(&self, buf: &mut String) { *buf += if *self { "Yes" } else { "No" }; } } } pub mod traits { pub trait GridIndex: Sized + Copy + Default { type T: Copy; const AROUND: [Self::T; 8]; fn add(self, rhs: Self::T) -> Self; fn around4(self) -> [Self; 4] { let mut res = [Self::default(); 4]; for i in 0..4 { res[i] = self.add(Self::AROUND[2*i]); } res } fn around8(self) -> [Self; 8] { let mut res = [Self::default(); 8]; for i in 0..8 { res[i] = self.add(Self::AROUND[i]); } res } fn rotate(self, l: usize, n: i32) -> Self; } impl GridIndex for [usize; 2] { type T = [isize; 2]; const AROUND: [Self::T; 8] = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]; fn add(self, rhs: Self::T) -> Self { [self[0].wrapping_add_signed(rhs[0]), self[1].wrapping_add_signed(rhs[1])] } fn rotate(self, l: usize, mut n: i32) -> Self { let [i, j] = self; n = n.div_euclid(4); if n == 0 { self } else if n == 1 { [j, l-1-i] } else if n == 2 { [l-1-i, l-1-j] } else { [l-1-j, i] } } } impl GridIndex for (usize, usize) { type T = (isize, isize); const AROUND: [Self::T; 8] = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]; fn add(self, rhs: Self::T) -> Self { (self.0.wrapping_add_signed(rhs.0), self.1.wrapping_add_signed(rhs.1)) } fn rotate(self, l: usize, mut n: i32) -> Self { let (i, j) = self; n = n.div_euclid(4); if n == 0 { self } else if n == 1 { (j, l-1-i) } else if n == 2 { (l-1-i, l-1-j) } else { (l-1-j, i) } } } pub trait CharUtil: Clone { const LOWER: [Self; 26]; const UPPER: [Self; 26]; const NUMBER: [Self; 10]; fn lower_to_us(self) -> usize; fn upper_to_us(self) -> usize; fn parse_us(self) -> usize; fn flip(self) -> Self; fn as_urdl(self) -> usize; } impl CharUtil for char { const LOWER: [char; 26] = { let (mut out, mut i) = (['_'; 26], 0); while i < 26 { out[i] = (i+97) as u8 as char; i += 1; } out }; const UPPER: [char; 26] = { let (mut out, mut i) = (['_'; 26], 0); while i < 26 { out[i] = (i+65) as u8 as char; i += 1; } out }; const NUMBER: [char; 10] = { let (mut res, mut i) = (['_'; 10], 0); while i < 10 { res[i] = (i+48) as u8 as char; i += 1; } res }; fn lower_to_us(self) -> usize { debug_assert!('a' <= self && self <= 'z'); self as usize - 97 } fn upper_to_us(self) -> usize { debug_assert!('A' <= self && self <= 'Z'); self as usize - 65 } fn parse_us(self) -> usize { self as usize - 48 } fn flip(self) -> Self { (self as u8 ^ 32) as char } fn as_urdl(self) -> usize { [b'U', b'R', b'D', b'L'].iter().position(|&v| v == self as u8 & 32).unwrap() } } } pub mod macros { #[macro_export] macro_rules! epr { ($($args:tt)*) => { if !$crate::SUBMISSION { #[allow(unused_mut)] let mut tmp = format!($($args)*); eprintln!("\x1b[31m{tmp}\x1b[0m"); } } } #[macro_export] macro_rules! oj_local { ($oj:expr, $local:expr) => { if $crate::SUBMISSION { $oj } else { $local } }; } #[macro_export] macro_rules! nest { [void; $n:expr] => { std::vec![std::vec![]; $n] }; [void; $n:expr $(;$m:expr)+] => { std::vec![nest![void$(;$m)+]; $n] }; [$($v:expr),*] => { std::vec![$($v),*] }; [$e:expr; $n:expr] => { std::vec![$e; $n] }; [$e:expr; $n:expr $(;$m:expr)+] => { std::vec![nest![$e$(;$m)+]; $n] }; } #[macro_export] macro_rules! min { ($($vl:expr),+) => { [$($vl),+].into_iter().reduce(|x,y| if x <= y {x} else {y}).unwrap() } } #[macro_export] macro_rules! max { ($($vl:expr),+) => { [$($vl),+].into_iter().reduce(|x,y| if x >= y {x} else {y}).unwrap() } } #[macro_export] macro_rules! chmin { ($dst:expr; $v:expr) => { { let v = $v; if v < $dst { $dst = v; true } else { false } } }; ($dst:expr; $($vl:expr),+) => { crate::chmin!($dst; crate::min!($($vl),+)) } } #[macro_export] macro_rules! chmax { ($dst:expr; $v:expr) => { { let v = $v; if $dst < v { $dst = v; true } else { false } } }; ($dst:expr; $($vl:expr),+) => { crate::chmax!($dst; crate::max!($($vl),+)) } } #[macro_export] macro_rules! safe_pow { ($v:expr, $e:expr) => { { let (mut v, mut e, mut res) = ($v, $e, 1); if e == 0 {1} else if v == 0 {0} else { while e != 0 { if e%2 == 1 { res = res.saturating_mul(v); } v = v.saturating_mul(v); e /= 2; } res } } }; ($v:expr, $e:expr, $m:expr) => { { let (mut v, mut e, m, mut res) = ($v, $e, $m, 1); if e == 0 {1%m} else if v == 0 {0} else { while e != 0 { if e%2 == 1 { res = (res*v)%m; } v = v*v%m; e /= 2; } res.rem_euclid(m) } } } } /* macro_rules! impl_for { ($trait:ty; $($type:ty),+) => { $( impl $trait for $type {} )+ } } pub(crate) use impl_for; */ } pub mod func { use std::ops::{RangeBounds, Bound}; pub fn binary_search(low: usize, high: usize) -> Option<usize> { if 1 < high.wrapping_sub(low) { Some(low.wrapping_add(high)/2) } else { None } } pub fn to_bounds(range: impl RangeBounds<usize>, sup: usize) -> [usize; 2] { let mut l = match range.start_bound() { Bound::Included(&v) => v, Bound::Excluded(&v) => v+1, Bound::Unbounded => 0 }; let mut r = match range.end_bound() { Bound::Included(&v) => v+1, Bound::Excluded(&v) => v, Bound::Unbounded => sup }; if l >= r { l = 0; r = 0; } assert!(r <= sup, "valid: 0..{sup}, input: {l}..{r}"); [l, r] } pub(crate) fn join(s: impl Iterator<Item = String>) -> Option<String> { let mut res = s.into_iter().fold(String::new(), |mut acc, e| { acc += &e; acc += ", "; acc }); if res.is_empty() { return None; } res.truncate(res.len() - 2); Some(res) } } } }
mod external { pub use { proconio::{ input, input_interactive, marker::{Bytes as bytes, Chars as chars, Usize1 as u1} }, }; }