結果

問題 No.2289 順列ソート
ユーザー tipstar0125tipstar0125
提出日時 2023-05-11 12:42:53
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 17,824 bytes
コンパイル時間 26,057 ms
コンパイル使用メモリ 377,612 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 11:34:37
合計ジャッジ時間 19,139 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
use std::cmp::Reverse;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};
const MOD: usize = 1e9 as usize + 7;
// const MOD: usize = 998244353;
// const MOD: usize = 2147483647;
// use lazy_static::lazy_static;
// lazy_static! {
// static ref N: usize= {
// input! { n: usize }
// n
// };
// // static ref _INPUT: (usize, usize) = {
// // input! { n: usize, m: usize, }
// // (n, m)
// // };
// // static ref N: usize = _INPUT.0;
// // static ref M: usize = _INPUT.1;
// }
#[derive(Default)]
struct Solver {}
impl Solver {
fn solve(&mut self) {
input! {}
}
}
fn main() {
std::thread::Builder::new()
.stack_size(128 * 1024 * 1024)
.spawn(|| Solver::default().solve())
.unwrap()
.join()
.unwrap();
}
// fn read<T: std::str::FromStr>() -> T {
// let mut s = String::new();
// std::io::stdin().read_line(&mut s).ok();
// s.trim().parse().ok().unwrap()
// }
// fn read_vec<T: std::str::FromStr>() -> Vec<T> {
// read::<String>()
// .split_whitespace()
// .map(|e| e.parse().ok().unwrap())
// .collect()
// }
#[macro_export]
macro_rules! input {
() => {};
(mut $var:ident: $t:tt, $($rest:tt)*) => {
let mut $var = __input_inner!($t);
input!($($rest)*)
};
($var:ident: $t:tt, $($rest:tt)*) => {
let $var = __input_inner!($t);
input!($($rest)*)
};
(mut $var:ident: $t:tt) => {
let mut $var = __input_inner!($t);
};
($var:ident: $t:tt) => {
let $var = __input_inner!($t);
};
}
#[macro_export]
macro_rules! __input_inner {
(($($t:tt),*)) => {
($(__input_inner!($t)),*)
};
([$t:tt; $n:expr]) => {
(0..$n).map(|_| __input_inner!($t)).collect::<Vec<_>>()
};
([$t:tt]) => {{
let n = __input_inner!(usize);
(0..n).map(|_| __input_inner!($t)).collect::<Vec<_>>()
}};
(chars) => {
__input_inner!(String).chars().collect::<Vec<_>>()
};
(bytes) => {
__input_inner!(String).into_bytes()
};
(usize1) => {
__input_inner!(usize) - 1
};
($t:ty) => {
$crate::read::<$t>()
};
}
#[macro_export]
macro_rules! println {
() => {
$crate::write(|w| {
use std::io::Write;
std::writeln!(w).unwrap()
})
};
($($arg:tt)*) => {
$crate::write(|w| {
use std::io::Write;
std::writeln!(w, $($arg)*).unwrap()
})
};
}
#[macro_export]
macro_rules! print {
($($arg:tt)*) => {
$crate::write(|w| {
use std::io::Write;
std::write!(w, $($arg)*).unwrap()
})
};
}
#[macro_export]
macro_rules! flush {
() => {
$crate::write(|w| {
use std::io::Write;
w.flush().unwrap()
})
};
}
pub fn read<T>() -> T
where
T: std::str::FromStr,
T::Err: std::fmt::Debug,
{
use std::cell::RefCell;
use std::io::*;
thread_local! {
pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
}
STDIN.with(|r| {
let mut r = r.borrow_mut();
let mut s = vec![];
loop {
let buf = r.fill_buf().unwrap();
if buf.is_empty() {
break;
}
if let Some(i) = buf.iter().position(u8::is_ascii_whitespace) {
s.extend_from_slice(&buf[..i]);
r.consume(i + 1);
if !s.is_empty() {
break;
}
} else {
s.extend_from_slice(buf);
let n = buf.len();
r.consume(n);
}
}
std::str::from_utf8(&s).unwrap().parse().unwrap()
})
}
pub fn write<F>(f: F)
where
F: FnOnce(&mut std::io::BufWriter<std::io::StdoutLock>),
{
use std::cell::RefCell;
use std::io::*;
thread_local! {
pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> =
RefCell::new(BufWriter::new(stdout().lock()));
}
STDOUT.with(|w| f(&mut w.borrow_mut()))
}
trait Bound<T> {
fn lower_bound(&self, x: &T) -> usize;
fn upper_bound(&self, x: &T) -> usize;
}
impl<T: PartialOrd> Bound<T> for [T] {
fn lower_bound(&self, x: &T) -> usize {
let (mut low, mut high) = (0, self.len());
while low + 1 < high {
let mid = (low + high) / 2;
if self[mid] < *x {
low = mid;
} else {
high = mid;
}
}
if self[low] < *x {
low + 1
} else {
low
}
}
fn upper_bound(&self, x: &T) -> usize {
let (mut low, mut high) = (0, self.len());
while low + 1 < high {
let mid = (low + high) / 2;
if self[mid] <= *x {
low = mid;
} else {
high = mid;
}
}
if self[low] <= *x {
low + 1
} else {
low
}
}
}
// mod rnd {
// use rand::Rng;
// static mut S: usize = 0;
// static MAX: usize = 1e9 as usize;
// #[inline]
// pub fn init(seed: usize) {
// unsafe {
// if seed == 0 {
// S = rand::thread_rng().gen();
// } else {
// S = seed;
// }
// }
// }
// #[inline]
// pub fn gen() -> usize {
// unsafe {
// if S == 0 {
// init(0);
// }
// S ^= S << 7;
// S ^= S >> 9;
// S
// }
// }
// #[inline]
// pub fn gen_range(a: usize, b: usize) -> usize {
// gen() % (b - a) + a
// }
// #[inline]
// pub fn gen_bool() -> bool {
// gen() & 1 == 1
// }
// #[inline]
// pub fn gen_float() -> f64 {
// ((gen() % MAX) as f64) / MAX as f64
// }
// }
#[macro_export]
macro_rules! max {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::max($x, max!($( $y ),+))
}
}
#[macro_export]
macro_rules! min {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::min($x, min!($( $y ),+))
}
}
#[derive(Debug, Clone)]
struct UnionFind {
parent: Vec<isize>,
roots: BTreeSet<usize>,
size: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let mut roots = BTreeSet::new();
for i in 0..n {
roots.insert(i);
}
UnionFind {
parent: vec![-1; n],
roots,
size: n,
}
}
fn find(&mut self, x: usize) -> usize {
if self.parent[x] < 0 {
return x;
}
let root = self.find(self.parent[x] as usize);
self.parent[x] = root as isize;
root
}
fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
let root_x = self.find(x);
let root_y = self.find(y);
if root_x == root_y {
return None;
}
let size_x = -self.parent[root_x];
let size_y = -self.parent[root_y];
self.size -= 1;
if size_x >= size_y {
self.parent[root_x] -= size_y;
self.parent[root_y] = root_x as isize;
self.roots.remove(&root_y);
Some((root_x, root_y))
} else {
self.parent[root_y] -= size_x;
self.parent[root_x] = root_y as isize;
self.roots.remove(&root_x);
Some((root_y, root_x))
}
}
fn is_same(&mut self, x: usize, y: usize) -> bool {
self.find(x) == self.find(y)
}
fn is_root(&mut self, x: usize) -> bool {
self.find(x) == x
}
fn get_union_size(&mut self, x: usize) -> usize {
let root = self.find(x);
-self.parent[root] as usize
}
fn get_size(&self) -> usize {
self.size
}
fn members(&mut self, x: usize) -> Vec<usize> {
let root = self.find(x);
(0..self.parent.len())
.filter(|i| self.find(*i) == root)
.collect::<Vec<usize>>()
}
fn all_group_members(&mut self) -> BTreeMap<usize, Vec<usize>> {
let mut groups_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for x in 0..self.parent.len() {
let r = self.find(x);
groups_map.entry(r).or_default().push(x);
}
groups_map
}
}
#[derive(Debug, Clone)]
struct WeightedUnionFind {
parent: Vec<isize>,
size: usize,
diff_weight: Vec<isize>,
}
impl WeightedUnionFind {
fn new(n: usize) -> Self {
WeightedUnionFind {
parent: vec![-1; n],
size: n,
diff_weight: vec![0_isize; n],
}
}
fn find(&mut self, x: usize) -> usize {
if self.parent[x] < 0 {
return x;
}
let root = self.find(self.parent[x] as usize);
self.diff_weight[x] += self.diff_weight[self.parent[x] as usize];
self.parent[x] = root as isize;
root
}
fn weight(&mut self, x: usize) -> isize {
self.find(x);
self.diff_weight[x]
}
fn unite(&mut self, x: usize, y: usize, w: isize) -> Option<(usize, usize)> {
let root_x = self.find(x);
let root_y = self.find(y);
if root_x == root_y {
return None;
}
let adjusted_w = w + self.weight(x) - self.weight(y);
let size_x = -self.parent[root_x];
let size_y = -self.parent[root_y];
self.size -= 1;
if size_x >= size_y {
self.diff_weight[root_y] = adjusted_w;
self.parent[root_x] -= size_y;
self.parent[root_y] = root_x as isize;
Some((root_x, root_y))
} else {
self.diff_weight[root_x] = -adjusted_w;
self.parent[root_y] -= size_x;
self.parent[root_x] = root_y as isize;
Some((root_y, root_x))
}
}
fn is_same(&mut self, x: usize, y: usize) -> bool {
self.find(x) == self.find(y)
}
fn is_root(&mut self, x: usize) -> bool {
self.find(x) == x
}
fn diff(&mut self, x: usize, y: usize) -> isize {
self.weight(y) - self.weight(x)
}
fn get_union_size(&mut self, x: usize) -> usize {
let root = self.find(x);
-self.parent[root] as usize
}
fn get_size(&self) -> usize {
self.size
}
fn roots(&self) -> Vec<usize> {
(0..self.parent.len())
.filter(|i| self.parent[*i] < 0)
.collect::<Vec<usize>>()
}
fn members(&mut self, x: usize) -> Vec<usize> {
let root = self.find(x);
(0..self.parent.len())
.filter(|i| self.find(*i) == root)
.collect::<Vec<usize>>()
}
fn all_group_members(&mut self) -> BTreeMap<usize, Vec<usize>> {
let mut groups_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for x in 0..self.parent.len() {
let r = self.find(x);
groups_map.entry(r).or_default().push(x);
}
groups_map
}
}
type Mod = ModInt;
#[derive(Debug, Clone, Copy, Default)]
struct ModInt {
value: usize,
}
impl ModInt {
fn new(n: usize) -> Self {
ModInt { value: n % MOD }
}
fn zero() -> Self {
ModInt { value: 0 }
}
fn one() -> Self {
ModInt { value: 1 }
}
fn value(&self) -> usize {
self.value
}
fn pow(&self, n: usize) -> Self {
let mut p = *self;
let mut ret = ModInt::one();
let mut nn = n;
while nn > 0 {
if nn & 1 == 1 {
ret *= p;
}
p *= p;
nn >>= 1;
}
ret
}
fn inv(&self) -> Self {
ModInt::new((ext_gcd(self.value, MOD).0 + MOD as isize) as usize)
}
}
impl std::ops::Add for ModInt {
type Output = ModInt;
fn add(self, other: Self) -> Self {
ModInt::new(self.value + other.value)
}
}
impl std::ops::Sub for ModInt {
type Output = ModInt;
fn sub(self, other: Self) -> Self {
ModInt::new(MOD + self.value - other.value)
}
}
impl std::ops::Mul for ModInt {
type Output = ModInt;
fn mul(self, other: Self) -> Self {
ModInt::new(self.value * other.value)
}
}
#[allow(clippy::suspicious_arithmetic_impl)]
impl std::ops::Div for ModInt {
type Output = ModInt;
fn div(self, other: Self) -> Self {
self * other.inv()
}
}
impl std::ops::AddAssign for ModInt {
fn add_assign(&mut self, other: Self) {
*self = *self + other;
}
}
impl std::ops::SubAssign for ModInt {
fn sub_assign(&mut self, other: Self) {
*self = *self - other;
}
}
impl std::ops::MulAssign for ModInt {
fn mul_assign(&mut self, other: Self) {
*self = *self * other;
}
}
impl std::ops::DivAssign for ModInt {
fn div_assign(&mut self, other: Self) {
*self = *self / other;
}
}
#[derive(Debug, Clone)]
struct Comb {
fact: Vec<ModInt>,
fact_inverse: Vec<ModInt>,
}
impl Comb {
fn new(n: usize) -> Self {
let mut fact = vec![Mod::one(), Mod::one()];
let mut fact_inverse = vec![Mod::one(), Mod::one()];
let mut inverse = vec![Mod::zero(), Mod::one()];
for i in 2..=n {
fact.push(*fact.last().unwrap() * Mod::new(i));
inverse.push((Mod::zero() - inverse[MOD % i]) * Mod::new(MOD / i));
fact_inverse.push(*fact_inverse.last().unwrap() * *inverse.last().unwrap());
}
Comb { fact, fact_inverse }
}
fn nCr(&self, n: usize, r: usize) -> ModInt {
self.fact[n] * self.fact_inverse[n - r] * self.fact_inverse[r]
}
fn nHr(&self, n: usize, r: usize) -> ModInt {
self.nCr(n + r - 1, r)
}
}
trait ArgOrd<T> {
fn argmax(&self) -> Option<usize>;
fn argmin(&self) -> Option<usize>;
}
impl<T: Ord> ArgOrd<T> for [T] {
fn argmax(&self) -> Option<usize> {
(0..self.len()).max_by_key(|&i| &self[i])
}
fn argmin(&self) -> Option<usize> {
(0..self.len()).min_by_key(|&i| &self[i])
}
}
fn eratosthenes(n: usize) -> Vec<bool> {
let mut is_prime_list = vec![true; n + 1];
is_prime_list[0] = false;
is_prime_list[1] = false;
let mut i = 2;
while i * i <= n {
if is_prime_list[i] {
let mut j = i * i;
while j <= n {
is_prime_list[j] = false;
j += i;
}
}
i += 1
}
is_prime_list
}
fn legendre(n: usize, p: usize) -> usize {
let mut cnt = 0_usize;
let mut pp = p;
while pp <= n {
cnt += n / pp;
pp *= p;
}
cnt
}
fn mod_pow(a: usize, b: usize) -> usize {
let mut p = a;
let mut ret = 1;
let mut n = b;
while n > 0 {
if n & 1 == 1 {
ret = ret * p % MOD;
}
p = p * p % MOD;
n >>= 1;
}
ret
}
fn mod_pow2(a: usize, b: usize, m: usize) -> usize {
let mut p = a;
let mut ret = 1;
let mut n = b;
while n > 0 {
if n & 1 == 1 {
ret = ret * p % m;
}
p = p * p % m;
n >>= 1;
}
ret
}
fn mod_inv(a: usize, b: usize) -> usize {
(a * mod_pow(b, MOD - 2)) % MOD
}
fn prime_factorize(n: usize) -> BTreeMap<usize, usize> {
let mut nn = n;
let mut i = 2;
let mut pf: BTreeMap<usize, usize> = BTreeMap::new();
while i * i <= n {
while nn % i == 0 {
*pf.entry(i).or_default() += 1;
nn /= i;
}
i += 1;
}
if nn != 1 {
*pf.entry(nn).or_default() += 1;
}
pf
}
fn enum_dividers(n: usize) -> Vec<usize> {
let mut i = 1_usize;
let mut ret = vec![];
while i * i <= n {
if n % i == 0 {
ret.push(i);
if i != n / i {
ret.push(n / i);
}
}
i += 1;
}
ret.sort();
ret
}
// ax+by=gcd(a, b)
fn ext_gcd(a: usize, b: usize) -> (isize, isize, usize) {
if a == 0 {
return (0, 1, b);
}
let (x, y, g) = ext_gcd(b % a, a);
(y - b as isize / a as isize * x, x, g)
}
fn mod_inv2(x: usize) -> usize {
(ext_gcd(x, MOD).0 + MOD as isize) as usize % MOD
}
fn coordinate_compression<T: std::cmp::Ord + Copy>(v: Vec<T>) -> BTreeMap<T, usize> {
let mut vv = v;
vv.sort();
vv.dedup();
let ret = vv.iter().enumerate().map(|(i, &s)| (s, i)).collect();
ret
}
fn transpose_vec<T>(v: Vec<Vec<T>>) -> Vec<Vec<T>> {
assert!(!v.is_empty());
let len = v[0].len();
let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
(0..len)
.map(|_| {
iters
.iter_mut()
.map(|n| n.next().unwrap())
.collect::<Vec<T>>()
})
.collect()
}
fn transpose_vec_deque<T>(v: VecDeque<VecDeque<T>>) -> VecDeque<VecDeque<T>> {
assert!(!v.is_empty());
let len = v[0].len();
let mut iters: VecDeque<_> = v.into_iter().map(|n| n.into_iter()).collect();
(0..len)
.map(|_| {
iters
.iter_mut()
.map(|n| n.next().unwrap())
.collect::<VecDeque<T>>()
})
.collect()
}
fn run_length_encoding<T: Eq>(v: Vec<T>) -> Vec<(T, usize)> {
let mut v = v.into_iter().map(|v| (v, 1)).collect::<Vec<_>>();
v.dedup_by(|a, b| {
a.0 == b.0 && {
b.1 += a.1;
true
}
});
v
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0