QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #795253 | #9805. Guide Map | ucup-team296# | AC ✓ | 720ms | 113532kb | Rust | 85.5kb | 2024-11-30 18:58:23 | 2024-11-30 18:58:24 |
Judging History
answer
// https://contest.ucup.ac/contest/1865/problem/9805
pub mod solution {
//{"name":"H. Guide Map","group":"Universal Cup - The 3rd Universal Cup. Stage 19: Shenyang","url":"https://contest.ucup.ac/contest/1865/problem/9805","interactive":false,"timeLimit":1000,"tests":[{"input":"4\n1 4\n2 3\n","output":"6\n"},{"input":"2\n","output":"2\n"}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"HGuideMap"}}}
use crate::algo_lib::collections::dsu::DSU;
use crate::algo_lib::collections::iter_ext::iter_copied::ItersCopied;
use crate::algo_lib::collections::segment_tree::Pushable;
use crate::algo_lib::collections::segment_tree::QueryResult;
use crate::algo_lib::collections::segment_tree::SegmentTree;
use crate::algo_lib::collections::segment_tree::SegmentTreeNode;
use crate::algo_lib::collections::slice_ext::bounds::Bounds;
use crate::algo_lib::collections::slice_ext::indices::Indices;
use crate::algo_lib::collections::vec_ext::inc_dec::IncDec;
use crate::algo_lib::graph::dfs_order::DFSOrder;
use crate::algo_lib::graph::dfs_order::DFSOrderTrait;
use crate::algo_lib::graph::edges::bi_edge::BiEdge;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
use crate::algo_lib::graph::Graph;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::recursive_function::Callable2;
use crate::algo_lib::misc::recursive_function::Callable3;
use crate::algo_lib::misc::recursive_function::RecursiveFunction2;
use crate::algo_lib::misc::recursive_function::RecursiveFunction3;
use crate::algo_lib::misc::test_type::TaskType;
use crate::algo_lib::misc::test_type::TestType;
use crate::algo_lib::numbers::mod_int::ModIntF;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::algo_lib::numbers::number_ext::Power;
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
let n = input.read_size();
let edges = input.read_size_pair_vec(n - 2).dec();
let mut dsu = DSU::new(n);
for (u, v) in edges.copy_iter() {
dsu.join(u, v);
}
let mut v0 = Vec::new();
let mut v1 = Vec::new();
for i in 0..n {
if dsu.get(i) == dsu.get(0) {
v0.push(i);
} else {
v1.push(i);
}
}
let mut g1 = Graph::new(v0.len());
let mut g2 = Graph::new(v1.len());
for (u, v) in edges.copy_iter() {
if dsu.get(u) == dsu.get(0) {
g1.add_edge(BiEdge::new(v0.lower_bound(&u), v0.lower_bound(&v)));
} else {
g2.add_edge(BiEdge::new(v1.lower_bound(&u), v1.lower_bound(&v)));
}
}
type Mod = ModIntF;
let mut c = vec![0; v0.len()];
let mut dfs = RecursiveFunction3::new(|f, vert: usize, prev: usize, q: usize| {
c[vert] = q;
for e in &g1[vert] {
if e.to() == prev {
continue;
}
f.call(e.to(), vert, q + v1.len() - v1.lower_bound(&v0[e.to()]));
}
});
dfs.call(0, 0, 0);
// let powers = powers(Mod::new(2), n + 1);
let mut answers = Vec::new();
for graph in [g1, g2] {
#[derive(Default)]
struct Node {
children: Vec<usize>,
}
impl SegmentTreeNode for Node {
fn new(_left: usize, _right: usize) -> Self {
Self::default()
}
fn join(&mut self, _left_val: &Self, _right_val: &Self) {}
fn accumulate(&mut self, _value: &Self) {}
fn reset_delta(&mut self) {}
}
impl Pushable<&usize> for Node {
fn push(&mut self, delta: &usize) {
self.children.push(*delta);
}
}
impl QueryResult<usize, usize> for Node {
fn empty_result(_args: &usize) -> usize {
0
}
fn result(&self, args: &usize) -> usize {
self.children.len() - self.children.upper_bound(args)
}
fn join_results(
left_res: usize,
right_res: usize,
_args: &usize,
_left: usize,
_mid: usize,
_right: usize,
) -> usize {
left_res + right_res
}
}
let mut answer1 = vec![0; graph.vertex_count()];
let mut answer3 = vec![0; graph.vertex_count()];
let DFSOrder { position, end } = graph.dfs_order();
let mut st = SegmentTree::<Node>::new(graph.vertex_count());
for i in 0..graph.vertex_count() {
st.point_through_update(position[i], &i);
}
let mut dfs = RecursiveFunction2::new(|f, vert: usize, prev: usize| -> usize {
let mut cur = 0;
for e in &graph[vert] {
if e.to() == prev {
continue;
}
cur += f.call(e.to(), vert);
}
answer1[vert] = cur;
cur += st.query_with_args(position[vert]..end[vert], &vert);
answer3[vert] = cur;
cur
});
dfs.call(0, 0);
let mut answer2 = vec![0; graph.vertex_count()];
let mut dfs = RecursiveFunction3::new(|f, vert: usize, prev: usize, additional: usize| {
answer2[vert] = answer1[vert] + additional;
for e in &graph[vert] {
if e.to() == prev {
continue;
}
let call_add = additional + answer1[vert] - answer3[e.to()]
+ st.query_with_args(..position[e.to()], &vert)
+ st.query_with_args(end[e.to()].., &vert);
f.call(e.to(), vert, call_add);
}
});
dfs.call(0, 0, 0);
answers.push(answer2);
}
let mut ans = Mod::zero();
if v1.len() == 1 {
ans += Mod::new(2).power(answers[0][0]);
}
let mut by = Mod::zero();
for i in v1.indices() {
by += Mod::new(2).power(answers[0][0] + answers[1][i] + v1.len() - i - 1);
}
for i in v0.indices() {
ans += by * Mod::new(2).power(c[i]);
}
out.print_line(ans);
}
pub static TEST_TYPE: TestType = TestType::Single;
pub static TASK_TYPE: TaskType = TaskType::Classic;
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
let mut pre_calc = ();
match TEST_TYPE {
TestType::Single => solve(&mut input, &mut output, 1, &mut pre_calc),
TestType::MultiNumber => {
let t = input.read();
for i in 1..=t {
solve(&mut input, &mut output, i, &mut pre_calc);
}
}
TestType::MultiEof => {
let mut i = 1;
while input.peek().is_some() {
solve(&mut input, &mut output, i, &mut pre_calc);
i += 1;
}
}
}
output.flush();
match TASK_TYPE {
TaskType::Classic => input.is_empty(),
TaskType::Interactive => true,
}
}
}
pub mod algo_lib {
#![allow(clippy::too_many_arguments)]
#![allow(clippy::type_complexity)]
#![allow(clippy::missing_safety_doc)]
#![allow(clippy::legacy_numeric_constants)]
pub mod collections {
pub mod bounds {
use std::ops::RangeBounds;
pub fn clamp(range: impl RangeBounds<usize>, n: usize) -> (usize, usize) {
let start = match range.start_bound() {
std::ops::Bound::Included(&x) => x,
std::ops::Bound::Excluded(&x) => x + 1,
std::ops::Bound::Unbounded => 0,
};
let end = match range.end_bound() {
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
std::ops::Bound::Unbounded => n,
};
(start, end.min(n))
}
}
pub mod dsu {
use crate::algo_lib::collections::iter_ext::collect::IterCollect;
use crate::algo_lib::collections::slice_ext::bounds::Bounds;
use crate::algo_lib::collections::slice_ext::indices::Indices;
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use std::cell::Cell;
#[derive(Clone)]
pub struct DSU {
id: Vec<Cell<u32>>,
size: Vec<u32>,
count: usize,
}
impl DSU {
pub fn new(n: usize) -> Self {
Self {
id: (0..n).map(|i| Cell::new(i as u32)).collect_vec(),
size: vec![1; n],
count: n,
}
}
pub fn size(&self, i: usize) -> usize {
self.size[self.get(i)] as usize
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.id.len()
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.id.iter().enumerate().filter_map(|(i, id)| {
if (i as u32) == id.get() {
Some(i)
} else {
None
}
})
}
pub fn set_count(&self) -> usize {
self.count
}
pub fn join(&mut self, mut a: usize, mut b: usize) -> bool {
a = self.get(a);
b = self.get(b);
if a == b {
false
} else {
self.size[a] += self.size[b];
self.id[b].replace(a as u32);
self.count -= 1;
true
}
}
pub fn get(&self, i: usize) -> usize {
if self.id[i].get() != i as u32 {
let res = self.get(self.id[i].get() as usize);
self.id[i].replace(res as u32);
}
self.id[i].get() as usize
}
pub fn clear(&mut self) {
self.count = self.id.len();
self.size.legacy_fill(1);
self.id.iter().enumerate().for_each(|(i, id)| {
id.replace(i as u32);
});
}
pub fn parts(&self) -> Vec<Vec<usize>> {
let roots = self.iter().collect_vec();
let mut res = vec![Vec::new(); roots.len()];
for i in self.id.indices() {
res[roots.as_slice().bin_search(&self.get(i)).unwrap()].push(i);
}
res
}
}
}
pub mod fx_hash_map {
// Copyright 2015 The Rust Project Developers. See the COPYRIGHT at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
use std::cell::Cell;
use std::convert::TryInto;
use std::time::SystemTime;
use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::BuildHasherDefault;
use std::hash::Hasher;
use std::mem::size_of;
use std::ops::BitXor;
pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
#[derive(Default)]
pub struct FxHasher {
hash: usize,
}
thread_local! {
static K: Cell<usize> = Cell::new(
((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos().wrapping_mul(2) + 1) & 0xFFFFFFFFFFFFFFFF) as usize
);
}
impl FxHasher {
#[inline]
fn add_to_hash(&mut self, i: usize) {
self.hash = self
.hash
.rotate_left(5)
.bitxor(i)
.wrapping_mul(K.with(|k| k.get()));
}
}
impl Hasher for FxHasher {
#[inline]
fn write(&mut self, mut bytes: &[u8]) {
let read_usize = |bytes: &[u8]| u64::from_ne_bytes(bytes[..8].try_into().unwrap());
let mut hash = FxHasher { hash: self.hash };
while bytes.len() >= size_of::<usize>() {
hash.add_to_hash(read_usize(bytes) as usize);
bytes = &bytes[size_of::<usize>()..];
}
if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
hash.add_to_hash(u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as usize);
bytes = &bytes[4..];
}
if (size_of::<usize>() > 2) && bytes.len() >= 2 {
hash.add_to_hash(u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as usize);
bytes = &bytes[2..];
}
if (size_of::<usize>() > 1) && !bytes.is_empty() {
hash.add_to_hash(bytes[0] as usize);
}
self.hash = hash.hash;
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u16(&mut self, i: u16) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.add_to_hash(i);
}
#[inline]
fn finish(&self) -> u64 {
self.hash as u64
}
}
}
pub mod iter_ext {
pub mod collect {
pub trait IterCollect<T>: Iterator<Item = T> + Sized {
fn collect_vec(self) -> Vec<T> {
self.collect()
}
}
impl<T, I: Iterator<Item = T> + Sized> IterCollect<T> for I {}
}
pub mod iter_copied {
use std::iter::Chain;
use std::iter::Copied;
use std::iter::Enumerate;
use std::iter::Filter;
use std::iter::Map;
use std::iter::Rev;
use std::iter::Skip;
use std::iter::StepBy;
use std::iter::Sum;
use std::iter::Take;
use std::iter::Zip;
pub trait ItersCopied<'a, T: 'a + Copy>: Sized + 'a
where
&'a Self: IntoIterator<Item = &'a T>,
{
fn copy_iter(&'a self) -> Copied<<&'a Self as IntoIterator>::IntoIter> {
self.into_iter().copied()
}
fn copy_enumerate(&'a self) -> Enumerate<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().enumerate()
}
fn copy_rev(&'a self) -> Rev<Copied<<&'a Self as IntoIterator>::IntoIter>>
where
Copied<<&'a Self as IntoIterator>::IntoIter>: DoubleEndedIterator,
{
self.copy_iter().rev()
}
fn copy_skip(&'a self, n: usize) -> Skip<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().skip(n)
}
fn copy_take(&'a self, n: usize) -> Take<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().take(n)
}
fn copy_chain<V>(
&'a self,
chained: &'a V,
) -> Chain<
Copied<<&'a Self as IntoIterator>::IntoIter>,
Copied<<&'a V as IntoIterator>::IntoIter>,
>
where
&'a V: IntoIterator<Item = &'a T>,
{
self.copy_iter().chain(chained.into_iter().copied())
}
fn copy_zip<V>(
&'a self,
other: &'a V,
) -> Zip<Copied<<&'a Self as IntoIterator>::IntoIter>, Copied<<&'a V as IntoIterator>::IntoIter>>
where
&'a V: IntoIterator<Item = &'a T>,
{
self.copy_iter().zip(other.into_iter().copied())
}
fn copy_max(&'a self) -> T
where
T: Ord,
{
self.copy_iter().max().unwrap()
}
fn copy_max_by_key<B, F>(&'a self, f: F) -> T
where
F: FnMut(&T) -> B,
B: Ord,
{
self.copy_iter().max_by_key(f).unwrap()
}
fn copy_min(&'a self) -> T
where
T: Ord,
{
self.copy_iter().min().unwrap()
}
fn copy_min_by_key<B, F>(&'a self, f: F) -> T
where
F: FnMut(&T) -> B,
B: Ord,
{
self.copy_iter().min_by_key(f).unwrap()
}
fn copy_sum(&'a self) -> T
where
T: Sum<T>,
{
self.copy_iter().sum()
}
fn copy_map<F, U>(&'a self, f: F) -> Map<Copied<<&'a Self as IntoIterator>::IntoIter>, F>
where
F: FnMut(T) -> U,
{
self.copy_iter().map(f)
}
fn copy_all(&'a self, f: impl FnMut(T) -> bool) -> bool {
self.copy_iter().all(f)
}
fn copy_any(&'a self, f: impl FnMut(T) -> bool) -> bool {
self.copy_iter().any(f)
}
fn copy_step_by(&'a self, step: usize) -> StepBy<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().step_by(step)
}
fn copy_filter<F: FnMut(&T) -> bool>(
&'a self,
f: F,
) -> Filter<Copied<<&'a Self as IntoIterator>::IntoIter>, F> {
self.copy_iter().filter(f)
}
fn copy_fold<Acc, F>(&'a self, init: Acc, f: F) -> Acc
where
F: FnMut(Acc, T) -> Acc,
{
self.copy_iter().fold(init, f)
}
fn copy_reduce<F>(&'a self, f: F) -> Option<T>
where
F: FnMut(T, T) -> T,
{
self.copy_iter().reduce(f)
}
fn copy_position<P>(&'a self, predicate: P) -> Option<usize>
where
P: FnMut(T) -> bool,
{
self.copy_iter().position(predicate)
}
}
impl<'a, U: 'a, T: 'a + Copy> ItersCopied<'a, T> for U where &'a U: IntoIterator<Item = &'a T> {}
}
}
pub mod segment_tree {
use crate::algo_lib::collections::bounds::clamp;
use crate::algo_lib::misc::direction::Direction;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::when;
use std::marker::PhantomData;
use std::ops::Add;
use std::ops::MulAssign;
use std::ops::RangeBounds;
pub trait SegmentTreeNode {
fn new(left: usize, right: usize) -> Self;
fn join(&mut self, left_val: &Self, right_val: &Self);
fn accumulate(&mut self, value: &Self);
fn reset_delta(&mut self);
}
pub trait Pushable<T>: SegmentTreeNode {
fn push(&mut self, delta: T);
}
impl<T: SegmentTreeNode> Pushable<&T> for T {
fn push(&mut self, delta: &T) {
self.accumulate(delta);
}
}
impl<T: SegmentTreeNode> Pushable<T> for T {
fn push(&mut self, delta: T) {
*self = delta;
}
}
pub trait QueryResult<Result, Args>: SegmentTreeNode {
fn empty_result(args: &Args) -> Result;
fn result(&self, args: &Args) -> Result;
fn join_results(
left_res: Result,
right_res: Result,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Result;
}
impl<T: SegmentTreeNode + Clone> QueryResult<T, ()> for T {
fn empty_result(_: &()) -> T {
Self::new(0, 0)
}
fn result(&self, _: &()) -> T {
self.clone()
}
fn join_results(left_res: T, right_res: T, _: &(), left: usize, mid: usize, right: usize) -> T {
when! {
left == mid => right_res,
right == mid => left_res,
else => {
let mut res = Self::new(left, right);
res.join(&left_res, &right_res);
res
},
}
}
}
impl<
Key: Add<Output = Key> + MulAssign<Delta> + Zero + Copy,
Delta: MulAssign<Delta> + One + Copy,
> SegmentTreeNode for (Key, Delta)
{
fn new(_left: usize, _right: usize) -> Self {
(Key::zero(), Delta::one())
}
fn join(&mut self, left_val: &Self, right_val: &Self) {
self.0 = left_val.0 + right_val.0;
}
fn accumulate(&mut self, value: &Self) {
self.0 *= value.1;
self.1 *= value.1;
}
fn reset_delta(&mut self) {
self.1 = Delta::one();
}
}
#[derive(Clone)]
pub struct SegmentTree<Node> {
n: usize,
nodes: Vec<Node>,
}
impl<Node: SegmentTreeNode> SegmentTree<Node> {
pub fn new(n: usize) -> Self {
Self::from_generator(n, |left| Node::new(left, left + 1))
}
pub fn from_array(arr: Vec<Node>) -> Self {
let n = arr.len();
let mut iter = arr.into_iter();
Self::from_generator(n, |_| iter.next().unwrap())
}
pub fn from_generator<F>(n: usize, gen: F) -> Self
where
F: FnMut(usize) -> Node,
{
if n == 0 {
return Self {
n,
nodes: vec![Node::new(0, 0)],
};
}
let mut res = Self {
n,
nodes: Vec::with_capacity(2 * n - 1),
};
res.init(gen);
res
}
fn init<F>(&mut self, mut f: F)
where
F: FnMut(usize) -> Node,
{
self.init_impl(2 * self.n - 2, 0, self.n, &mut f);
}
fn init_impl<F>(&mut self, root: usize, left: usize, right: usize, f: &mut F)
where
F: FnMut(usize) -> Node,
{
if left + 1 == right {
self.nodes.push(f(left));
} else {
let mid = left + ((right - left) >> 1);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
self.init_impl(left_child, left, mid, f);
self.init_impl(right_child, mid, right, f);
let mut node = Node::new(left, right);
node.join(&self.nodes[left_child], &self.nodes[right_child]);
self.nodes.push(node);
}
}
pub fn point_query(&mut self, at: usize) -> &Node {
assert!(at < self.n);
self.do_point_query(self.nodes.len() - 1, 0, self.n, at)
}
fn do_point_query(&mut self, root: usize, left: usize, right: usize, at: usize) -> &Node {
if left + 1 == right {
&self.nodes[root]
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_query(left_child, left, mid, at)
} else {
self.do_point_query(right_child, mid, right, at)
}
}
}
pub fn point_update<T>(&mut self, at: usize, val: T)
where
Node: Pushable<T>,
{
assert!(at < self.n);
self.do_point_update(self.nodes.len() - 1, 0, self.n, at, val);
}
fn do_point_update<T>(&mut self, root: usize, left: usize, right: usize, at: usize, val: T)
where
Node: Pushable<T>,
{
if left + 1 == right {
self.nodes[root].push(val);
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_update(left_child, left, mid, at, val);
} else {
self.do_point_update(right_child, mid, right, at, val);
}
self.join(root, mid, right);
}
}
pub fn point_through_update<'a, T>(&mut self, at: usize, val: &'a T)
where
Node: Pushable<&'a T>,
{
assert!(at < self.n);
self.do_point_through_update(self.nodes.len() - 1, 0, self.n, at, val);
}
fn do_point_through_update<'a, T>(
&mut self,
root: usize,
left: usize,
right: usize,
at: usize,
val: &'a T,
) where
Node: Pushable<&'a T>,
{
self.nodes[root].push(val);
if left + 1 != right {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_through_update(left_child, left, mid, at, val);
} else {
self.do_point_through_update(right_child, mid, right, at, val);
}
}
}
pub fn point_operation<Args, Res>(
&mut self,
op: &mut dyn PointOperation<Node, Args, Res>,
args: Args,
) -> Res {
assert_ne!(self.n, 0);
self.do_point_operation(op, self.nodes.len() - 1, 0, self.n, args)
}
fn do_point_operation<Args, Res>(
&mut self,
op: &mut dyn PointOperation<Node, Args, Res>,
root: usize,
left: usize,
right: usize,
args: Args,
) -> Res {
if left + 1 == right {
op.adjust_leaf(&mut self.nodes[root], left, args)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let (l, r) = self.nodes.split_at_mut(root);
let (l, m) = l.split_at_mut(right_child);
let direction = op.select_branch(
&mut r[0],
&mut l[left_child],
&mut m[0],
&args,
left,
mid,
right,
);
let res = match direction {
Direction::Left => self.do_point_operation(op, left_child, left, mid, args),
Direction::Right => self.do_point_operation(op, right_child, mid, right, args),
};
self.join(root, mid, right);
res
}
}
pub fn update<'a, T>(&mut self, range: impl RangeBounds<usize>, val: &'a T)
where
Node: Pushable<&'a T>,
{
let (from, to) = clamp(range, self.n);
self.do_update(self.nodes.len() - 1, 0, self.n, from, to, val)
}
pub fn do_update<'a, T>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
val: &'a T,
) where
Node: Pushable<&'a T>,
{
when! {
left >= to || right <= from => {},
left >= from && right <= to => self.nodes[root].push(val),
else => {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
self.do_update(left_child, left, mid, from, to, val);
self.do_update(right_child, mid, right, from, to, val);
self.join(root, mid, right);
},
}
}
pub fn operation<Args, Res>(
&mut self,
range: impl RangeBounds<usize>,
op: &mut dyn Operation<Node, Args, Res>,
args: &Args,
) -> Res {
let (from, to) = clamp(range, self.n);
self.do_operation(self.nodes.len() - 1, 0, self.n, from, to, op, args)
}
pub fn do_operation<Args, Res>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
op: &mut dyn Operation<Node, Args, Res>,
args: &Args,
) -> Res {
when! {
left >= to || right <= from => op.empty_result(left, right, args),
left >= from && right <= to => op.process_result(&mut self.nodes[root], args),
else => {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let left_result = self.do_operation(left_child, left, mid, from, to, op, args);
let right_result = self.do_operation(right_child, mid, right, from, to, op, args);
self.join(root, mid, right);
op.join_results(left_result, right_result, args)
},
}
}
pub fn binary_search<Res>(
&mut self,
wh: impl FnMut(&Node, &Node) -> Direction,
calc: impl FnMut(&Node, usize) -> Res,
) -> Res {
self.do_binary_search(self.nodes.len() - 1, 0, self.n, wh, calc)
}
fn do_binary_search<Res>(
&mut self,
root: usize,
left: usize,
right: usize,
mut wh: impl FnMut(&Node, &Node) -> Direction,
mut calc: impl FnMut(&Node, usize) -> Res,
) -> Res {
if left + 1 == right {
calc(&self.nodes[root], left)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let direction = wh(&self.nodes[left_child], &self.nodes[right_child]);
match direction {
Direction::Left => self.do_binary_search(left_child, left, mid, wh, calc),
Direction::Right => self.do_binary_search(right_child, mid, right, wh, calc),
}
}
}
fn join(&mut self, root: usize, mid: usize, right: usize) {
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let (left_node, right_node) = self.nodes.split_at_mut(root);
right_node[0].join(&left_node[left_child], &left_node[right_child]);
}
fn do_push_down(&mut self, parent: usize, to: usize) {
let (left_nodes, right_nodes) = self.nodes.split_at_mut(parent);
left_nodes[to].accumulate(&right_nodes[0]);
}
fn push_down(&mut self, root: usize, mid: usize, right: usize) {
self.do_push_down(root, root - 2 * (right - mid));
self.do_push_down(root, root - 1);
self.nodes[root].reset_delta();
}
pub fn query<T>(&mut self, range: impl RangeBounds<usize>) -> T
where
Node: QueryResult<T, ()>,
{
let (from, to) = clamp(range, self.n);
if from >= to {
Node::empty_result(&())
} else {
self.do_query(self.nodes.len() - 1, 0, self.n, from, to, &())
}
}
pub fn query_with_args<T, Args>(&mut self, range: impl RangeBounds<usize>, args: &Args) -> T
where
Node: QueryResult<T, Args>,
{
let (from, to) = clamp(range, self.n);
if from >= to {
Node::empty_result(args)
} else {
self.do_query(self.nodes.len() - 1, 0, self.n, from, to, args)
}
}
fn do_query<T, Args>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
args: &Args,
) -> T
where
Node: QueryResult<T, Args>,
{
if left >= from && right <= to {
self.nodes[root].result(args)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
when! {
to <= mid => self.do_query(left_child, left, mid, from, to, args),
from >= mid => self.do_query(right_child, mid, right, from, to, args),
else => {
let left_result = self.do_query(left_child, left, mid, from, to, args);
let right_result = self.do_query(right_child, mid, right, from, to, args);
Node::join_results(left_result, right_result, args, left, mid, right)
},
}
}
}
}
pub trait PointOperation<Node: SegmentTreeNode, Args, Res = Node> {
fn adjust_leaf(&mut self, leaf: &mut Node, at: usize, args: Args) -> Res;
fn select_branch(
&mut self,
root: &mut Node,
left_child: &mut Node,
right_child: &mut Node,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Direction;
}
pub struct PointOperationClosure<'s, Node: SegmentTreeNode, Args, Res = Node> {
adjust_leaf: Box<dyn FnMut(&mut Node, usize, Args) -> Res + 's>,
select_branch: Box<
dyn FnMut(&mut Node, &mut Node, &mut Node, &Args, usize, usize, usize) -> Direction + 's,
>,
phantom_node: PhantomData<Node>,
phantom_args: PhantomData<Args>,
phantom_res: PhantomData<Res>,
}
impl<'s, Node: SegmentTreeNode, Args, Res> PointOperationClosure<'s, Node, Args, Res> {
pub fn new<F1, F2>(adjust_leaf: F1, select_branch: F2) -> Self
where
F1: FnMut(&mut Node, usize, Args) -> Res + 's,
F2: FnMut(&mut Node, &mut Node, &mut Node, &Args, usize, usize, usize) -> Direction + 's,
{
Self {
adjust_leaf: Box::new(adjust_leaf),
select_branch: Box::new(select_branch),
phantom_node: Default::default(),
phantom_args: Default::default(),
phantom_res: Default::default(),
}
}
}
impl<'s, Node: SegmentTreeNode, Args, Res> PointOperation<Node, Args, Res>
for PointOperationClosure<'s, Node, Args, Res>
{
fn adjust_leaf(&mut self, leaf: &mut Node, at: usize, args: Args) -> Res {
(self.adjust_leaf)(leaf, at, args)
}
fn select_branch(
&mut self,
root: &mut Node,
left_child: &mut Node,
right_child: &mut Node,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Direction {
(self.select_branch)(root, left_child, right_child, args, left, mid, right)
}
}
pub trait Operation<Node: SegmentTreeNode, Args, Res = Node> {
fn process_result(&mut self, node: &mut Node, args: &Args) -> Res;
fn join_results(&mut self, left_res: Res, right_res: Res, args: &Args) -> Res;
fn empty_result(&mut self, left: usize, right: usize, args: &Args) -> Res;
}
pub struct OperationClosure<'s, Node: SegmentTreeNode, Args, Res = Node> {
process_result: Box<dyn FnMut(&mut Node, &Args) -> Res + 's>,
join_results: Box<dyn FnMut(Res, Res, &Args) -> Res + 's>,
empty_result: Box<dyn FnMut(usize, usize, &Args) -> Res + 's>,
phantom_node: PhantomData<Node>,
phantom_args: PhantomData<Args>,
phantom_res: PhantomData<Res>,
}
impl<'s, Node: SegmentTreeNode, Args, Res> OperationClosure<'s, Node, Args, Res> {
pub fn new<F1, F2, F3>(process_result: F1, join_results: F2, empty_result: F3) -> Self
where
F1: FnMut(&mut Node, &Args) -> Res + 's,
F2: FnMut(Res, Res, &Args) -> Res + 's,
F3: FnMut(usize, usize, &Args) -> Res + 's,
{
Self {
process_result: Box::new(process_result),
join_results: Box::new(join_results),
empty_result: Box::new(empty_result),
phantom_node: Default::default(),
phantom_args: Default::default(),
phantom_res: Default::default(),
}
}
}
impl<'s, Node: SegmentTreeNode, Args, Res> Operation<Node, Args, Res>
for OperationClosure<'s, Node, Args, Res>
{
fn process_result(&mut self, node: &mut Node, args: &Args) -> Res {
(self.process_result)(node, args)
}
fn join_results(&mut self, left_res: Res, right_res: Res, args: &Args) -> Res {
(self.join_results)(left_res, right_res, args)
}
fn empty_result(&mut self, left: usize, right: usize, args: &Args) -> Res {
(self.empty_result)(left, right, args)
}
}
}
pub mod slice_ext {
pub mod bounds {
pub trait Bounds<T: PartialOrd> {
fn lower_bound(&self, el: &T) -> usize;
fn upper_bound(&self, el: &T) -> usize;
fn bin_search(&self, el: &T) -> Option<usize>;
fn more(&self, el: &T) -> usize;
fn more_or_eq(&self, el: &T) -> usize;
fn less(&self, el: &T) -> usize;
fn less_or_eq(&self, el: &T) -> usize;
}
impl<T: PartialOrd> Bounds<T> for [T] {
fn lower_bound(&self, el: &T) -> usize {
let mut left = 0;
let mut right = self.len();
while left < right {
let mid = left + ((right - left) >> 1);
if &self[mid] < el {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn upper_bound(&self, el: &T) -> usize {
let mut left = 0;
let mut right = self.len();
while left < right {
let mid = left + ((right - left) >> 1);
if &self[mid] <= el {
left = mid + 1;
} else {
right = mid;
}
}
left
}
fn bin_search(&self, el: &T) -> Option<usize> {
let at = self.lower_bound(el);
if at == self.len() || &self[at] != el {
None
} else {
Some(at)
}
}
fn more(&self, el: &T) -> usize {
self.len() - self.upper_bound(el)
}
fn more_or_eq(&self, el: &T) -> usize {
self.len() - self.lower_bound(el)
}
fn less(&self, el: &T) -> usize {
self.lower_bound(el)
}
fn less_or_eq(&self, el: &T) -> usize {
self.upper_bound(el)
}
}
}
pub mod indices {
use std::ops::Range;
pub trait Indices {
fn indices(&self) -> Range<usize>;
}
impl<T> Indices for [T] {
fn indices(&self) -> Range<usize> {
0..self.len()
}
}
}
pub mod legacy_fill {
// 1.50
pub trait LegacyFill<T> {
fn legacy_fill(&mut self, val: T);
}
impl<T: Clone> LegacyFill<T> for [T] {
fn legacy_fill(&mut self, val: T) {
for el in self.iter_mut() {
*el = val.clone();
}
}
}
}
}
pub mod vec_ext {
pub mod default {
pub fn default_vec<T: Default>(len: usize) -> Vec<T> {
let mut v = Vec::with_capacity(len);
for _ in 0..len {
v.push(T::default());
}
v
}
}
pub mod inc_dec {
use crate::algo_lib::numbers::num_traits::algebra::AdditionMonoidWithSub;
use crate::algo_lib::numbers::num_traits::algebra::One;
pub trait IncDec {
#[must_use]
fn inc(self) -> Self;
#[must_use]
fn dec(self) -> Self;
}
impl<T: AdditionMonoidWithSub + One> IncDec for T {
fn inc(self) -> Self {
self + T::one()
}
fn dec(self) -> Self {
self - T::one()
}
}
impl<T: AdditionMonoidWithSub + One> IncDec for Vec<T> {
fn inc(mut self) -> Self {
self.iter_mut().for_each(|i| *i += T::one());
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|i| *i -= T::one());
self
}
}
impl<T: AdditionMonoidWithSub + One> IncDec for Vec<Vec<T>> {
fn inc(mut self) -> Self {
self.iter_mut()
.for_each(|v| v.iter_mut().for_each(|i| *i += T::one()));
self
}
fn dec(mut self) -> Self {
self.iter_mut()
.for_each(|v| v.iter_mut().for_each(|i| *i -= T::one()));
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One> IncDec for Vec<(T, U)> {
fn inc(mut self) -> Self {
self.iter_mut().for_each(|(i, j)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|(i, j)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V> IncDec for Vec<(T, U, V)> {
fn inc(mut self) -> Self {
self.iter_mut().for_each(|(i, j, _)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|(i, j, _)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V, W> IncDec
for Vec<(T, U, V, W)>
{
fn inc(mut self) -> Self {
self.iter_mut().for_each(|(i, j, ..)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|(i, j, ..)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One, V, W, X> IncDec
for Vec<(T, U, V, W, X)>
{
fn inc(mut self) -> Self {
self.iter_mut().for_each(|(i, j, ..)| {
*i += T::one();
*j += U::one();
});
self
}
fn dec(mut self) -> Self {
self.iter_mut().for_each(|(i, j, ..)| {
*i -= T::one();
*j -= U::one();
});
self
}
}
impl<T: AdditionMonoidWithSub + One, U: AdditionMonoidWithSub + One> IncDec for (T, U) {
fn inc(mut self) -> Self {
self.0 += T::one();
self.1 += U::one();
self
}
fn dec(mut self) -> Self {
self.0 -= T::one();
self.1 -= U::one();
self
}
}
}
}
}
pub mod graph {
use crate::algo_lib::collections::dsu::DSU;
use crate::algo_lib::graph::edges::bi_edge::BiEdge;
use crate::algo_lib::graph::edges::edge::Edge;
use crate::algo_lib::graph::edges::edge_trait::BidirectionalEdgeTrait;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
use std::ops::Index;
use std::ops::IndexMut;
#[derive(Clone)]
pub struct Graph<E: EdgeTrait> {
edges: Vec<Vec<E>>,
edge_count: usize,
}
impl<E: EdgeTrait> Graph<E> {
pub fn new(vertex_count: usize) -> Self {
Self {
edges: vec![Vec::new(); vertex_count],
edge_count: 0,
}
}
pub fn add_edge(&mut self, (from, mut edge): (usize, E)) -> usize {
let to = edge.to();
assert!(to < self.vertex_count());
let direct_id = self.edges[from].len();
edge.set_id(self.edge_count);
self.edges[from].push(edge);
if E::REVERSABLE {
let rev_id = self.edges[to].len();
self.edges[from][direct_id].set_reverse_id(rev_id);
let mut rev_edge = self.edges[from][direct_id].reverse_edge(from);
rev_edge.set_id(self.edge_count);
rev_edge.set_reverse_id(direct_id);
self.edges[to].push(rev_edge);
}
self.edge_count += 1;
direct_id
}
pub fn add_vertices(&mut self, cnt: usize) {
self.edges.resize(self.edges.len() + cnt, Vec::new());
}
pub fn clear(&mut self) {
self.edge_count = 0;
for ve in self.edges.iter_mut() {
ve.clear();
}
}
pub fn vertex_count(&self) -> usize {
self.edges.len()
}
pub fn edge_count(&self) -> usize {
self.edge_count
}
pub fn degrees(&self) -> Vec<usize> {
self.edges.iter().map(|v| v.len()).collect()
}
}
impl<E: BidirectionalEdgeTrait> Graph<E> {
pub fn is_tree(&self) -> bool {
if self.edge_count + 1 != self.vertex_count() {
false
} else {
self.is_connected()
}
}
pub fn is_forest(&self) -> bool {
let mut dsu = DSU::new(self.vertex_count());
for i in 0..self.vertex_count() {
for e in self[i].iter() {
if i <= e.to() && !dsu.join(i, e.to()) {
return false;
}
}
}
true
}
pub fn is_connected(&self) -> bool {
let mut dsu = DSU::new(self.vertex_count());
for i in 0..self.vertex_count() {
for e in self[i].iter() {
dsu.join(i, e.to());
}
}
dsu.set_count() == 1
}
}
impl<E: EdgeTrait> Index<usize> for Graph<E> {
type Output = [E];
fn index(&self, index: usize) -> &Self::Output {
&self.edges[index]
}
}
impl<E: EdgeTrait> IndexMut<usize> for Graph<E> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.edges[index]
}
}
impl Graph<Edge<()>> {
pub fn from_edges(n: usize, edges: &[(usize, usize)]) -> Self {
let mut graph = Self::new(n);
for &(from, to) in edges {
graph.add_edge(Edge::new(from, to));
}
graph
}
}
impl<P: Clone> Graph<Edge<P>> {
pub fn from_edges_with_payload(n: usize, edges: &[(usize, usize, P)]) -> Self {
let mut graph = Self::new(n);
for (from, to, p) in edges.iter() {
graph.add_edge(Edge::with_payload(*from, *to, p.clone()));
}
graph
}
}
impl Graph<BiEdge<()>> {
pub fn from_biedges(n: usize, edges: &[(usize, usize)]) -> Self {
let mut graph = Self::new(n);
for &(from, to) in edges {
graph.add_edge(BiEdge::new(from, to));
}
graph
}
}
impl<P: Clone> Graph<BiEdge<P>> {
pub fn from_biedges_with_payload(n: usize, edges: &[(usize, usize, P)]) -> Self {
let mut graph = Self::new(n);
for (from, to, p) in edges.iter() {
graph.add_edge(BiEdge::with_payload(*from, *to, p.clone()));
}
graph
}
}
pub mod dfs_order {
use crate::algo_lib::graph::edges::edge_trait::BidirectionalEdgeTrait;
use crate::algo_lib::graph::Graph;
pub struct DFSOrder {
pub position: Vec<usize>,
pub end: Vec<usize>,
}
pub trait DFSOrderTrait {
fn dfs_order_with_root(&self, root: usize) -> DFSOrder;
fn dfs_order(&self) -> DFSOrder {
self.dfs_order_with_root(0)
}
}
impl<E: BidirectionalEdgeTrait> DFSOrderTrait for Graph<E> {
fn dfs_order_with_root(&self, root: usize) -> DFSOrder {
debug_assert!(self.is_tree());
let count = self.vertex_count();
let mut position = vec![0; count];
let mut end = vec![0; count];
let mut edge = vec![0u32; count];
let mut stack = vec![0u32; count];
let mut last = vec![0u32; count];
let mut size = 1usize;
last[root] = root as u32;
stack[0] = root as u32;
position[root] = 0;
let mut index = 0usize;
while size > 0 {
let current = stack[size - 1] as usize;
let c_edge = &mut edge[current];
if *c_edge == self[current].len() as u32 {
end[current] = index + 1;
size -= 1;
} else {
let next = self[current][*c_edge as usize].to();
*c_edge += 1;
if next == (last[current] as usize) {
continue;
}
index += 1;
position[next] = index;
last[next] = current as u32;
stack[size] = next as u32;
size += 1;
}
}
DFSOrder { position, end }
}
}
}
pub mod edges {
pub mod bi_edge {
use crate::algo_lib::graph::edges::bi_edge_trait::BiEdgeTrait;
use crate::algo_lib::graph::edges::edge_id::EdgeId;
use crate::algo_lib::graph::edges::edge_id::NoId;
use crate::algo_lib::graph::edges::edge_id::WithId;
use crate::algo_lib::graph::edges::edge_trait::BidirectionalEdgeTrait;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
#[derive(Clone)]
pub struct BiEdgeRaw<Id: EdgeId, P> {
to: u32,
id: Id,
payload: P,
}
impl<Id: EdgeId> BiEdgeRaw<Id, ()> {
pub fn new(from: usize, to: usize) -> (usize, Self) {
(
from,
Self {
to: to as u32,
id: Id::new(),
payload: (),
},
)
}
}
impl<Id: EdgeId, P> BiEdgeRaw<Id, P> {
pub fn with_payload(from: usize, to: usize, payload: P) -> (usize, Self) {
(from, Self::with_payload_impl(to, payload))
}
fn with_payload_impl(to: usize, payload: P) -> BiEdgeRaw<Id, P> {
Self {
to: to as u32,
id: Id::new(),
payload,
}
}
}
impl<Id: EdgeId, P: Clone> BidirectionalEdgeTrait for BiEdgeRaw<Id, P> {}
impl<Id: EdgeId, P: Clone> EdgeTrait for BiEdgeRaw<Id, P> {
type Payload = P;
const REVERSABLE: bool = true;
fn to(&self) -> usize {
self.to as usize
}
fn id(&self) -> usize {
self.id.id()
}
fn set_id(&mut self, id: usize) {
self.id.set_id(id);
}
fn reverse_id(&self) -> usize {
panic!("no reverse id")
}
fn set_reverse_id(&mut self, _: usize) {}
fn reverse_edge(&self, from: usize) -> Self {
Self::with_payload_impl(from, self.payload.clone())
}
fn payload(&self) -> &P {
&self.payload
}
}
impl<Id: EdgeId, P: Clone> BiEdgeTrait for BiEdgeRaw<Id, P> {}
pub type BiEdge<P> = BiEdgeRaw<NoId, P>;
pub type BiEdgeWithId<P> = BiEdgeRaw<WithId, P>;
}
pub mod bi_edge_trait {
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
pub trait BiEdgeTrait: EdgeTrait {}
}
pub mod edge {
use crate::algo_lib::graph::edges::edge_id::EdgeId;
use crate::algo_lib::graph::edges::edge_id::NoId;
use crate::algo_lib::graph::edges::edge_id::WithId;
use crate::algo_lib::graph::edges::edge_trait::EdgeTrait;
#[derive(Clone)]
pub struct EdgeRaw<Id: EdgeId, P> {
to: u32,
id: Id,
payload: P,
}
impl<Id: EdgeId> EdgeRaw<Id, ()> {
pub fn new(from: usize, to: usize) -> (usize, Self) {
(
from,
Self {
to: to as u32,
id: Id::new(),
payload: (),
},
)
}
}
impl<Id: EdgeId, P> EdgeRaw<Id, P> {
pub fn with_payload(from: usize, to: usize, payload: P) -> (usize, Self) {
(from, Self::with_payload_impl(to, payload))
}
fn with_payload_impl(to: usize, payload: P) -> Self {
Self {
to: to as u32,
id: Id::new(),
payload,
}
}
}
impl<Id: EdgeId, P: Clone> EdgeTrait for EdgeRaw<Id, P> {
type Payload = P;
const REVERSABLE: bool = false;
fn to(&self) -> usize {
self.to as usize
}
fn id(&self) -> usize {
self.id.id()
}
fn set_id(&mut self, id: usize) {
self.id.set_id(id);
}
fn reverse_id(&self) -> usize {
panic!("no reverse")
}
fn set_reverse_id(&mut self, _: usize) {
panic!("no reverse")
}
fn reverse_edge(&self, _: usize) -> Self {
panic!("no reverse")
}
fn payload(&self) -> &P {
&self.payload
}
}
pub type Edge<P> = EdgeRaw<NoId, P>;
pub type EdgeWithId<P> = EdgeRaw<WithId, P>;
}
pub mod edge_id {
pub trait EdgeId: Clone {
fn new() -> Self;
fn id(&self) -> usize;
fn set_id(&mut self, id: usize);
}
#[derive(Clone)]
pub struct WithId {
id: u32,
}
impl EdgeId for WithId {
fn new() -> Self {
Self { id: 0 }
}
fn id(&self) -> usize {
self.id as usize
}
fn set_id(&mut self, id: usize) {
self.id = id as u32;
}
}
#[derive(Clone)]
pub struct NoId {}
impl EdgeId for NoId {
fn new() -> Self {
Self {}
}
fn id(&self) -> usize {
panic!("Id called on no id")
}
fn set_id(&mut self, _: usize) {}
}
}
pub mod edge_trait {
pub trait EdgeTrait: Clone {
type Payload;
const REVERSABLE: bool;
fn to(&self) -> usize;
fn id(&self) -> usize;
fn set_id(&mut self, id: usize);
fn reverse_id(&self) -> usize;
fn set_reverse_id(&mut self, reverse_id: usize);
#[must_use]
fn reverse_edge(&self, from: usize) -> Self;
fn payload(&self) -> &Self::Payload;
}
pub trait BidirectionalEdgeTrait: EdgeTrait {}
}
}
}
pub mod io {
pub mod input {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::io::Read;
use std::mem::MaybeUninit;
pub struct Input<'s> {
input: &'s mut (dyn Read + Send),
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
macro_rules! read_impl {
($t: ty, $read_name: ident, $read_vec_name: ident) => {
pub fn $read_name(&mut self) -> $t {
self.read()
}
pub fn $read_vec_name(&mut self, len: usize) -> Vec<$t> {
self.read_vec(len)
}
};
($t: ty, $read_name: ident, $read_vec_name: ident, $read_pair_vec_name: ident) => {
read_impl!($t, $read_name, $read_vec_name);
pub fn $read_pair_vec_name(&mut self, len: usize) -> Vec<($t, $t)> {
self.read_vec(len)
}
};
}
impl<'s> Input<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(input: &'s mut (dyn Read + Send)) -> Self {
Self {
input,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
buf_read: 0,
}
}
pub fn new_with_size(input: &'s mut (dyn Read + Send), buf_size: usize) -> Self {
Self {
input,
buf: default_vec(buf_size),
at: 0,
buf_read: 0,
}
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
if res == b'\r' {
if self.refill_buffer() && self.buf[self.at] == b'\n' {
self.at += 1;
}
return Some(b'\n');
}
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
Some(if res == b'\r' { b'\n' } else { res })
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !b.is_ascii_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
//noinspection RsSelfConvention
pub fn is_empty(&mut self) -> bool {
self.skip_whitespace();
self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn read_vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0..size {
res.push(self.read());
}
res
}
pub fn read_char(&mut self) -> u8 {
self.skip_whitespace();
self.get().unwrap()
}
read_impl!(u32, read_unsigned, read_unsigned_vec);
read_impl!(u64, read_u64, read_u64_vec);
read_impl!(usize, read_size, read_size_vec, read_size_pair_vec);
read_impl!(i32, read_int, read_int_vec, read_int_pair_vec);
read_impl!(i64, read_long, read_long_vec, read_long_pair_vec);
read_impl!(i128, read_i128, read_i128_vec);
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for u8 {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.read_vec(size)
}
}
impl<T: Readable, const SIZE: usize> Readable for [T; SIZE] {
fn read(input: &mut Input) -> Self {
unsafe {
let mut res = MaybeUninit::<[T; SIZE]>::uninit();
for i in 0..SIZE {
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(i).write(input.read::<T>());
}
res.assume_init()
}
}
}
macro_rules! read_integer {
($($t:ident)+) => {$(
impl Readable for $t {
fn read(input: &mut Input) -> Self {
input.skip_whitespace();
let mut c = input.get().unwrap();
let sgn = match c {
b'-' => {
c = input.get().unwrap();
true
}
b'+' => {
c = input.get().unwrap();
false
}
_ => false,
};
let mut res = 0;
loop {
assert!(c.is_ascii_digit());
res *= 10;
let d = (c - b'0') as $t;
if sgn {
res -= d;
} else {
res += d;
}
match input.get() {
None => break,
Some(ch) => {
if ch.is_ascii_whitespace() {
break;
} else {
c = ch;
}
}
}
}
res
}
}
)+};
}
read_integer!(i8 i16 i32 i64 i128 isize u16 u32 u64 u128 usize);
macro_rules! tuple_readable {
($($name:ident)+) => {
impl<$($name: Readable), +> Readable for ($($name,)+) {
fn read(input: &mut Input) -> Self {
($($name::read(input),)+)
}
}
}
}
tuple_readable! {T}
tuple_readable! {T U}
tuple_readable! {T U V}
tuple_readable! {T U V X}
tuple_readable! {T U V X Y}
tuple_readable! {T U V X Y Z}
tuple_readable! {T U V X Y Z A}
tuple_readable! {T U V X Y Z A B}
tuple_readable! {T U V X Y Z A B C}
tuple_readable! {T U V X Y Z A B C D}
tuple_readable! {T U V X Y Z A B C D E}
tuple_readable! {T U V X Y Z A B C D E F}
impl Read for Input<'_> {
fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
if self.at == self.buf_read {
self.input.read(buf)
} else {
let mut i = 0;
while i < buf.len() && self.at < self.buf_read {
buf[i] = self.buf[self.at];
i += 1;
self.at += 1;
}
Ok(i)
}
}
}
}
pub mod output {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::cmp::Reverse;
use std::io::stderr;
use std::io::Stderr;
use std::io::Write;
#[derive(Copy, Clone)]
pub enum BoolOutput {
YesNo,
YesNoCaps,
PossibleImpossible,
Custom(&'static str, &'static str),
}
impl BoolOutput {
pub fn output(&self, output: &mut Output, val: bool) {
(if val { self.yes() } else { self.no() }).write(output);
}
fn yes(&self) -> &str {
match self {
BoolOutput::YesNo => "Yes",
BoolOutput::YesNoCaps => "YES",
BoolOutput::PossibleImpossible => "Possible",
BoolOutput::Custom(yes, _) => yes,
}
}
fn no(&self) -> &str {
match self {
BoolOutput::YesNo => "No",
BoolOutput::YesNoCaps => "NO",
BoolOutput::PossibleImpossible => "Impossible",
BoolOutput::Custom(_, no) => no,
}
}
}
pub struct Output<'s> {
output: &'s mut dyn Write,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
bool_output: BoolOutput,
precision: Option<usize>,
}
impl<'s> Output<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: false,
bool_output: BoolOutput::YesNoCaps,
precision: None,
}
}
pub fn new_with_auto_flush(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: true,
bool_output: BoolOutput::YesNoCaps,
precision: None,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.output.flush().unwrap();
self.at = 0;
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
self.maybe_flush();
}
pub fn print_line<T: Writable>(&mut self, s: T) {
self.print(s);
self.put(b'\n');
self.maybe_flush();
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
self.print_per_line_iter(arg.iter());
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn print_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
self.print_iter(iter);
self.put(b'\n');
}
pub fn print_per_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
for e in iter {
e.write(self);
self.put(b'\n');
}
}
pub fn set_bool_output(&mut self, bool_output: BoolOutput) {
self.bool_output = bool_output;
}
pub fn set_precision(&mut self, precision: usize) {
self.precision = Some(precision);
}
pub fn reset_precision(&mut self) {
self.precision = None;
}
pub fn get_precision(&self) -> Option<usize> {
self.precision
}
}
impl Write for Output<'_> {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
self.maybe_flush();
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl Writable for u8 {
fn write(&self, output: &mut Output) {
output.put(*self);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable, const N: usize> Writable for [T; N] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable + ?Sized> Writable for &T {
fn write(&self, output: &mut Output) {
T::write(self, output)
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self.as_slice().write(output);
}
}
impl Writable for () {
fn write(&self, _output: &mut Output) {}
}
macro_rules! write_to_string {
($($t:ident)+) => {$(
impl Writable for $t {
fn write(&self, output: &mut Output) {
self.to_string().write(output);
}
}
)+};
}
write_to_string!(u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
macro_rules! tuple_writable {
($name0:ident $($name:ident: $id:tt )*) => {
impl<$name0: Writable, $($name: Writable,)*> Writable for ($name0, $($name,)*) {
fn write(&self, out: &mut Output) {
self.0.write(out);
$(
out.put(b' ');
self.$id.write(out);
)*
}
}
}
}
tuple_writable! {T}
tuple_writable! {T U:1}
tuple_writable! {T U:1 V:2}
tuple_writable! {T U:1 V:2 X:3}
tuple_writable! {T U:1 V:2 X:3 Y:4}
tuple_writable! {T U:1 V:2 X:3 Y:4 Z:5}
tuple_writable! {T U:1 V:2 X:3 Y:4 Z:5 A:6}
tuple_writable! {T U:1 V:2 X:3 Y:4 Z:5 A:6 B:7}
tuple_writable! {T U:1 V:2 X:3 Y:4 Z:5 A:6 B:7 C:8}
impl<T: Writable> Writable for Option<T> {
fn write(&self, output: &mut Output) {
match self {
None => (-1).write(output),
Some(t) => t.write(output),
}
}
}
impl Writable for bool {
fn write(&self, output: &mut Output) {
let bool_output = output.bool_output;
bool_output.output(output, *self)
}
}
impl<T: Writable> Writable for Reverse<T> {
fn write(&self, output: &mut Output) {
self.0.write(output);
}
}
static mut ERR: Option<Stderr> = None;
pub fn err() -> Output<'static> {
unsafe {
if ERR.is_none() {
ERR = Some(stderr());
}
Output::new_with_auto_flush(ERR.as_mut().unwrap())
}
}
}
}
pub mod misc {
pub mod direction {
#[derive(Copy, Clone)]
pub enum Direction {
Left,
Right,
}
}
pub mod recursive_function {
use std::marker::PhantomData;
macro_rules! recursive_function {
($name: ident, $trait: ident, ($($type: ident $arg: ident,)*)) => {
pub trait $trait<$($type, )*Output> {
fn call(&mut self, $($arg: $type,)*) -> Output;
}
pub struct $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
f: std::cell::UnsafeCell<F>,
$($arg: PhantomData<$type>,
)*
phantom_output: PhantomData<Output>,
}
impl<F, $($type, )*Output> $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
pub fn new(f: F) -> Self {
Self {
f: std::cell::UnsafeCell::new(f),
$($arg: Default::default(),
)*
phantom_output: Default::default(),
}
}
}
impl<F, $($type, )*Output> $trait<$($type, )*Output> for $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
fn call(&mut self, $($arg: $type,)*) -> Output {
unsafe { (*self.f.get())(self, $($arg, )*) }
}
}
}
}
recursive_function!(RecursiveFunction0, Callable0, ());
recursive_function!(RecursiveFunction, Callable, (Arg arg,));
recursive_function!(RecursiveFunction2, Callable2, (Arg1 arg1, Arg2 arg2,));
recursive_function!(RecursiveFunction3, Callable3, (Arg1 arg1, Arg2 arg2, Arg3 arg3,));
recursive_function!(RecursiveFunction4, Callable4, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4,));
recursive_function!(RecursiveFunction5, Callable5, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5,));
recursive_function!(RecursiveFunction6, Callable6, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6,));
recursive_function!(RecursiveFunction7, Callable7, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7,));
recursive_function!(RecursiveFunction8, Callable8, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8,));
recursive_function!(RecursiveFunction9, Callable9, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8, Arg9 arg9,));
}
pub mod test_type {
pub enum TestType {
Single,
MultiNumber,
MultiEof,
}
pub enum TaskType {
Classic,
Interactive,
}
}
pub mod value {
use std::hash::Hash;
pub trait Value<T>: Copy + Eq + Hash {
fn val() -> T;
}
pub trait ConstValue<T>: Value<T> {
const VAL: T;
}
impl<T, V: ConstValue<T>> Value<T> for V {
fn val() -> T {
Self::VAL
}
}
#[macro_export]
macro_rules! value {
($name: ident: $t: ty = $val: expr) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Default)]
pub struct $name {}
impl $crate::algo_lib::misc::value::ConstValue<$t> for $name {
const VAL: $t = $val;
}
};
}
pub trait DynamicValue<T>: Value<T> {
//noinspection RsSelfConvention
fn set_val(t: T);
}
#[macro_export]
macro_rules! dynamic_value {
($name: ident: $t: ty, $val: ident) => {
static mut $val: Option<$t> = None;
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)]
struct $name {}
impl $crate::algo_lib::misc::value::DynamicValue<$t> for $name {
fn set_val(t: $t) {
unsafe {
$val = Some(t);
}
}
}
impl $crate::algo_lib::misc::value::Value<$t> for $name {
fn val() -> $t {
unsafe { $val.unwrap() }
}
}
};
($name: ident: $t: ty) => {
dynamic_value!($name: $t, VAL);
};
($name: ident: $t: ty = $val: expr) => {
dynamic_value!($name: $t);
$name::set_val($val);
};
($name: ident: $t: ty = $val: expr, $val_static: ident) => {
dynamic_value!($name: $t, $val_static);
$name::set_val($val);
};
}
}
pub mod when {
#[macro_export]
macro_rules! when {
{$($cond: expr => $then: expr,)*} => {
match () {
$(_ if $cond => $then,)*
_ => unreachable!(),
}
};
{$($cond: expr => $then: expr,)* else $(=>)? $else: expr$(,)?} => {
match () {
$(_ if $cond => $then,)*
_ => $else,
}
};
}
}
}
pub mod numbers {
pub mod gcd {
use crate::algo_lib::numbers::num_traits::algebra::IntegerMultiplicationMonoid;
use crate::algo_lib::numbers::num_traits::algebra::IntegerSemiRingWithSub;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::SemiRingWithSub;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::algo_lib::numbers::num_traits::wideable::Wideable;
use std::mem::swap;
pub fn extended_gcd<T: IntegerSemiRingWithSub + Wideable + Copy>(a: T, b: T) -> (T, T::W, T::W)
where
T::W: Copy + SemiRingWithSub,
{
if a == T::zero() {
(b, T::W::zero(), T::W::one())
} else {
let (d, y, mut x) = extended_gcd(b % a, a);
x -= T::W::from(b / a) * y;
(d, x, y)
}
}
pub fn gcd<T: Copy + Zero + IntegerMultiplicationMonoid>(mut a: T, mut b: T) -> T {
while b != T::zero() {
a %= b;
swap(&mut a, &mut b);
}
a
}
pub fn lcm<T: Copy + Zero + IntegerMultiplicationMonoid>(a: T, b: T) -> T {
(a / gcd(a, b)) * b
}
}
pub mod mod_int {
use crate::algo_lib::collections::fx_hash_map::FxHashMap;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::input::Readable;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::output::Writable;
use crate::algo_lib::misc::value::Value;
use crate::algo_lib::numbers::gcd::extended_gcd;
use crate::algo_lib::numbers::num_traits::algebra::Field;
use crate::algo_lib::numbers::num_traits::algebra::IntegerRing;
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Ring;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use crate::algo_lib::numbers::num_traits::wideable::Wideable;
use crate::value;
use crate::when;
use std::fmt::Display;
use std::fmt::Formatter;
use std::hash::Hash;
use std::marker::PhantomData;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Neg;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait BaseModInt: Field + Copy {
type W: IntegerRing + Copy + From<Self::T>;
type T: IntegerRing + Ord + Copy + Wideable<W = Self::W>;
fn from(v: Self::T) -> Self;
fn module() -> Self::T;
}
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)]
pub struct ModInt<T, V: Value<T>> {
n: T,
phantom: PhantomData<V>,
}
impl<T: Copy, V: Value<T>> ModInt<T, V> {
pub fn val(&self) -> T {
self.n
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> ModInt<T, V> {
unsafe fn unchecked_new(n: T) -> Self {
debug_assert!(n >= T::zero() && n < V::val());
Self {
n,
phantom: Default::default(),
}
}
unsafe fn maybe_subtract_mod(mut n: T) -> T {
debug_assert!(n < V::val() + V::val() && n >= T::zero());
if n >= V::val() {
n -= V::val();
}
n
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> ModInt<T, V> {
pub fn new(n: T) -> Self {
unsafe { Self::unchecked_new(Self::maybe_subtract_mod(n % (V::val()) + V::val())) }
}
}
impl<T: Copy + IntegerRing + Ord + Wideable + Hash, V: Value<T>> ModInt<T, V>
where
T::W: Copy + IntegerRing,
{
pub fn log(&self, alpha: Self) -> T {
let mut base = FxHashMap::default();
let mut exp = T::zero();
let mut pow = Self::one();
let mut inv = *self;
let alpha_inv = alpha.inv().unwrap();
while exp * exp < Self::module() {
if inv == Self::one() {
return exp;
}
base.insert(inv, exp);
exp += T::one();
pow *= alpha;
inv *= alpha_inv;
}
let step = pow;
let mut i = T::one();
loop {
if let Some(b) = base.get(&pow) {
break exp * i + *b;
}
pow *= step;
i += T::one();
}
}
}
impl<T: Wideable + Ring + Ord + Copy, V: Value<T>> ModInt<T, V>
where
T::W: IntegerRing,
{
pub fn new_from_wide(n: T::W) -> Self {
unsafe {
Self::unchecked_new(Self::maybe_subtract_mod(
T::downcast(n % V::val().into()) + V::val(),
))
}
}
}
impl<T: Copy + IntegerRing + Ord + Wideable, V: Value<T>> Invertible for ModInt<T, V>
where
T::W: Copy + IntegerRing,
{
type Output = Self;
fn inv(&self) -> Option<Self> {
let (g, x, _) = extended_gcd(self.n, V::val());
if g != T::one() {
None
} else {
Some(Self::new_from_wide(x))
}
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> BaseModInt for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type W = T::W;
type T = T;
fn from(v: Self::T) -> Self {
Self::new(v)
}
fn module() -> T {
V::val()
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> From<T> for ModInt<T, V> {
fn from(n: T) -> Self {
Self::new(n)
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> AddAssign for ModInt<T, V> {
fn add_assign(&mut self, rhs: Self) {
self.n = unsafe { Self::maybe_subtract_mod(self.n + rhs.n) };
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Add for ModInt<T, V> {
type Output = Self;
fn add(mut self, rhs: Self) -> Self::Output {
self += rhs;
self
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> SubAssign for ModInt<T, V> {
fn sub_assign(&mut self, rhs: Self) {
self.n = unsafe { Self::maybe_subtract_mod(self.n + V::val() - rhs.n) };
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Sub for ModInt<T, V> {
type Output = Self;
fn sub(mut self, rhs: Self) -> Self::Output {
self -= rhs;
self
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> MulAssign for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
fn mul_assign(&mut self, rhs: Self) {
self.n = T::downcast(T::W::from(self.n) * T::W::from(rhs.n) % T::W::from(V::val()));
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> Mul for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type Output = Self;
fn mul(mut self, rhs: Self) -> Self::Output {
self *= rhs;
self
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> DivAssign for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
#[allow(clippy::suspicious_op_assign_impl)]
fn div_assign(&mut self, rhs: Self) {
*self *= rhs.inv().unwrap();
}
}
impl<T: IntegerRing + Ord + Copy + Wideable, V: Value<T>> Div for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
type Output = Self;
fn div(mut self, rhs: Self) -> Self::Output {
self /= rhs;
self
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Neg for ModInt<T, V> {
type Output = Self;
fn neg(mut self) -> Self::Output {
self.n = unsafe { Self::maybe_subtract_mod(V::val() - self.n) };
self
}
}
impl<T: Display, V: Value<T>> Display for ModInt<T, V> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
<T as Display>::fmt(&self.n, f)
}
}
impl<T: IntegerRing + Ord + Copy + Readable, V: Value<T>> Readable for ModInt<T, V> {
fn read(input: &mut Input) -> Self {
Self::new(T::read(input))
}
}
impl<T: Writable, V: Value<T>> Writable for ModInt<T, V> {
fn write(&self, output: &mut Output) {
self.n.write(output);
}
}
impl<T: Ring + Ord + Copy, V: Value<T>> Zero for ModInt<T, V> {
fn zero() -> Self {
unsafe { Self::unchecked_new(T::zero()) }
}
}
impl<T: IntegerRing + Ord + Copy, V: Value<T>> One for ModInt<T, V> {
fn one() -> Self {
Self::new(T::one())
}
}
impl<T, V: Value<T>> Wideable for ModInt<T, V> {
type W = Self;
fn downcast(w: Self::W) -> Self {
w
}
}
impl<T: IntegerRing + Ord + Copy + Wideable + Display + AsIndex, V: Value<T>> std::fmt::Debug
for ModInt<T, V>
where
T::W: IntegerRing + Copy,
{
fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
let max = T::from_index(100);
when! {
self.n <= max => write!(f, "{}", self.n),
self.n >= V::val() - max => write!(f, "{}", self.n - V::val()),
else => {
let mut denominator = T::one();
while denominator < max {
let mut num = T::one();
while num < max {
if Self::new(num) / Self::new(denominator) == *self {
return write!(f, "{}/{}", num, denominator);
}
if -Self::new(num) / Self::new(denominator) == *self {
return write!(f, "-{}/{}", num, denominator);
}
num += T::one();
}
denominator += T::one();
}
write!(f, "(?? {} ??)", self.n)
},
}
}
}
impl<T: IntegerRing + Ord + Copy + AsIndex + Wideable, V: Value<T>> AsIndex for ModInt<T, V>
where
T::W: AsIndex + IntegerRing + Ord,
{
fn from_index(idx: usize) -> Self {
let t = T::W::from_index(idx);
if t >= T::W::from(V::val()) {
Self::new_from_wide(t)
} else {
unsafe { Self::unchecked_new(T::downcast(t)) }
}
}
fn to_index(self) -> usize {
self.n.to_index()
}
}
value!(Val7: i32 = 1_000_000_007);
pub type ModInt7 = ModInt<i32, Val7>;
value!(Val9: i32 = 1_000_000_009);
pub type ModInt9 = ModInt<i32, Val9>;
value!(ValF: i32 = 998_244_353);
pub type ModIntF = ModInt<i32, ValF>;
}
pub mod num_traits {
pub mod algebra {
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Neg;
use std::ops::Rem;
use std::ops::RemAssign;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
pub trait AdditionMonoid: Add<Output = Self> + AddAssign + Zero + Eq + Sized {}
impl<T: Add<Output = Self> + AddAssign + Zero + Eq> AdditionMonoid for T {}
pub trait AdditionMonoidWithSub: AdditionMonoid + Sub<Output = Self> + SubAssign {}
impl<T: AdditionMonoid + Sub<Output = Self> + SubAssign> AdditionMonoidWithSub for T {}
pub trait AdditionGroup: AdditionMonoidWithSub + Neg<Output = Self> {}
impl<T: AdditionMonoidWithSub + Neg<Output = Self>> AdditionGroup for T {}
pub trait MultiplicationMonoid: Mul<Output = Self> + MulAssign + One + Eq + Sized {}
impl<T: Mul<Output = Self> + MulAssign + One + Eq> MultiplicationMonoid for T {}
pub trait IntegerMultiplicationMonoid:
MultiplicationMonoid + Div<Output = Self> + Rem<Output = Self> + DivAssign + RemAssign
{
}
impl<T: MultiplicationMonoid + Div<Output = Self> + Rem<Output = Self> + DivAssign + RemAssign>
IntegerMultiplicationMonoid for T
{
}
pub trait MultiplicationGroup:
MultiplicationMonoid + Div<Output = Self> + DivAssign + Invertible<Output = Self>
{
}
impl<T: MultiplicationMonoid + Div<Output = Self> + DivAssign + Invertible<Output = Self>>
MultiplicationGroup for T
{
}
pub trait SemiRing: AdditionMonoid + MultiplicationMonoid {}
impl<T: AdditionMonoid + MultiplicationMonoid> SemiRing for T {}
pub trait SemiRingWithSub: AdditionMonoidWithSub + SemiRing {}
impl<T: AdditionMonoidWithSub + SemiRing> SemiRingWithSub for T {}
pub trait Ring: SemiRing + AdditionGroup {}
impl<T: SemiRing + AdditionGroup> Ring for T {}
pub trait IntegerSemiRing: SemiRing + IntegerMultiplicationMonoid {}
impl<T: SemiRing + IntegerMultiplicationMonoid> IntegerSemiRing for T {}
pub trait IntegerSemiRingWithSub: SemiRingWithSub + IntegerSemiRing {}
impl<T: SemiRingWithSub + IntegerSemiRing> IntegerSemiRingWithSub for T {}
pub trait IntegerRing: IntegerSemiRing + Ring {}
impl<T: IntegerSemiRing + Ring> IntegerRing for T {}
pub trait Field: Ring + MultiplicationGroup {}
impl<T: Ring + MultiplicationGroup> Field for T {}
macro_rules! zero_one_integer_impl {
($($t: ident)+) => {$(
impl Zero for $t {
fn zero() -> Self {
0
}
}
impl One for $t {
fn one() -> Self {
1
}
}
)+};
}
zero_one_integer_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod as_index {
pub trait AsIndex {
fn from_index(idx: usize) -> Self;
fn to_index(self) -> usize;
}
macro_rules! from_index_impl {
($($t: ident)+) => {$(
impl AsIndex for $t {
fn from_index(idx: usize) -> Self {
idx as $t
}
fn to_index(self) -> usize {
self as usize
}
}
)+};
}
from_index_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod invertible {
pub trait Invertible {
type Output;
fn inv(&self) -> Option<Self::Output>;
}
}
pub mod wideable {
use std::convert::From;
pub trait Wideable: Sized {
type W: From<Self>;
fn downcast(w: Self::W) -> Self;
}
macro_rules! wideable_impl {
($($t: ident $w: ident),+) => {$(
impl Wideable for $t {
type W = $w;
fn downcast(w: Self::W) -> Self {
w as $t
}
}
)+};
}
wideable_impl!(i64 i128, i32 i64, i16 i32, i8 i16, u64 u128, u32 u64, u16 u32, u8 u16);
}
}
pub mod number_ext {
use crate::algo_lib::numbers::num_traits::algebra::IntegerSemiRing;
use crate::algo_lib::numbers::num_traits::algebra::MultiplicationMonoid;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use std::ops::Mul;
pub trait Power {
#[must_use]
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self;
}
impl<S: MultiplicationMonoid + Copy> Power for S {
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self {
if exp == T::zero() {
S::one()
} else {
let mut res = self.power(exp / (T::one() + T::one()));
res *= res;
if exp % (T::one() + T::one()) == T::one() {
res *= *self;
}
res
}
}
}
pub trait NumDigs {
fn num_digs(&self) -> usize;
}
impl<S: IntegerSemiRing + AsIndex + Copy> NumDigs for S {
fn num_digs(&self) -> usize {
let mut copy = *self;
let ten = S::from_index(10);
let mut res = 0;
while copy != S::zero() {
copy /= ten;
res += 1;
}
res
}
}
pub trait SumDigs {
fn sum_digs(&self) -> Self;
}
impl<S: IntegerSemiRing + AsIndex + Copy> SumDigs for S {
fn sum_digs(&self) -> S {
let mut copy = *self;
let ten = S::from_index(10);
let mut res = S::zero();
while copy != S::zero() {
res += copy % ten;
copy /= ten;
}
res
}
}
pub trait Square {
fn square(self) -> Self;
}
impl<T: Mul<Output = T> + Copy> Square for T {
fn square(self) -> Self {
self * self
}
}
}
}
}
fn main() {
let mut sin = std::io::stdin();
let input = algo_lib::io::input::Input::new(&mut sin);
let mut stdout = std::io::stdout();
let output = algo_lib::io::output::Output::new(&mut stdout);
solution::run(input, output);
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2168kb
input:
4 1 4 2 3
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 2084kb
input:
2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 2284kb
input:
4 1 2 1 3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 2284kb
input:
4 1 3 3 2
output:
8
result:
ok 1 number(s): "8"
Test #5:
score: 0
Accepted
time: 0ms
memory: 2248kb
input:
4 1 4 4 2
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 0ms
memory: 2140kb
input:
4 1 2 3 4
output:
15
result:
ok 1 number(s): "15"
Test #7:
score: 0
Accepted
time: 0ms
memory: 2172kb
input:
4 3 2 2 4
output:
10
result:
ok 1 number(s): "10"
Test #8:
score: 0
Accepted
time: 6ms
memory: 3440kb
input:
5000 407 334 4311 4338 2530 2578 2052 1946 3803 3961 1849 1756 813 876 1417 1364 3955 3713 694 661 2682 2791 1626 1791 3913 3702 4068 4053 1239 1264 2848 2682 4995 4979 3609 3604 3496 3434 229 162 4178 4769 3908 3874 4891 4920 2401 2249 2682 2853 4294 4336 4494 4478 2815 2682 4925 4928 912 914 2257 ...
output:
574627696
result:
ok 1 number(s): "574627696"
Test #9:
score: 0
Accepted
time: 6ms
memory: 3432kb
input:
5000 4737 4822 2534 2241 724 710 1628 1749 4448 4435 3571 4046 4029 4064 4972 4949 4405 4346 3929 4150 630 546 207 246 3203 3182 880 877 2200 2306 4336 4365 74 126 3932 3777 4212 4210 753 418 4995 4960 274 644 3993 4081 1522 1458 1937 1887 3882 4124 3651 4038 2703 2630 1918 1912 2764 2832 171 137 48...
output:
844318380
result:
ok 1 number(s): "844318380"
Test #10:
score: 0
Accepted
time: 3ms
memory: 3272kb
input:
5000 4016 3910 4361 4417 3103 3026 4686 4701 595 592 3076 3071 859 931 4288 4262 4478 4452 4884 4982 3595 3550 2814 2821 3521 3437 872 925 3785 3836 1192 1094 4149 4133 3603 3467 2999 3031 2425 2289 379 376 932 952 1483 1436 144 190 2619 2630 2078 2067 3226 3173 2996 2931 4520 4461 2724 2790 2475 24...
output:
928056438
result:
ok 1 number(s): "928056438"
Test #11:
score: 0
Accepted
time: 7ms
memory: 3712kb
input:
5000 1714 1797 3971 4077 2321 2302 3844 3211 3852 3900 865 908 2586 2565 2311 2122 3320 3089 2113 2200 3101 3798 3192 3024 1687 1490 3194 3772 210 264 80 147 4309 4225 3017 2854 1861 1511 3207 3307 4395 4438 2138 2204 3459 3624 1670 1518 4175 3959 2087 2078 1128 1097 1770 1574 840 833 1298 1207 2056...
output:
289973060
result:
ok 1 number(s): "289973060"
Test #12:
score: 0
Accepted
time: 7ms
memory: 4264kb
input:
5000 4970 1539 4964 4066 3800 2291 3101 2220 4718 1242 4970 4489 3275 1183 1645 2209 4970 3628 1874 2720 3392 4356 1227 4970 306 1131 293 2057 1980 4500 336 3792 4970 4588 3826 3933 336 3786 3589 2148 717 1369 3589 3595 336 1916 4970 3447 4970 529 2570 4012 2049 4970 2282 336 3097 2495 4787 424 4970...
output:
747571707
result:
ok 1 number(s): "747571707"
Test #13:
score: 0
Accepted
time: 7ms
memory: 4188kb
input:
5000 2059 75 1737 2687 4712 2259 4792 2059 4990 3387 705 3561 4128 2059 2059 1676 2910 196 4371 4262 3332 3286 3168 2048 4368 2907 1154 3951 496 4358 4988 2059 2059 4905 4640 2155 318 3306 2492 2753 128 4624 239 919 1891 4990 2851 2622 2009 2059 4260 3788 3597 1389 1169 919 4691 4597 4990 4410 1826 ...
output:
728916312
result:
ok 1 number(s): "728916312"
Test #14:
score: 0
Accepted
time: 8ms
memory: 4352kb
input:
5000 28 964 2373 1620 1693 3860 2179 4699 3661 516 1420 4579 430 42 822 3550 4746 1837 498 4426 2887 725 1587 1731 4895 2648 1093 2701 985 626 1980 2449 4675 1550 1940 2309 2217 3178 2310 3364 3469 4708 4598 1729 93 1759 4061 2641 1420 2563 4349 2993 4411 2445 4710 728 4726 4188 2026 1291 4916 824 2...
output:
600365554
result:
ok 1 number(s): "600365554"
Test #15:
score: 0
Accepted
time: 3ms
memory: 4372kb
input:
5000 674 2007 3824 1699 2977 1519 4900 545 4798 4617 913 3691 4352 2068 164 2412 2018 4524 2306 672 389 2543 1114 4254 555 1250 1070 21 2850 4335 2977 1785 505 2092 1972 400 3727 3947 3050 25 3235 1158 4338 2130 2185 3824 1680 1370 770 4872 2977 4259 2624 398 4571 3666 3345 4674 4404 428 56 541 2561...
output:
117462685
result:
ok 1 number(s): "117462685"
Test #16:
score: 0
Accepted
time: 7ms
memory: 4472kb
input:
5000 536 1522 3240 4848 2425 680 4827 3759 2522 2634 3061 1006 1422 1374 4768 3745 4528 3589 995 3473 649 716 3738 3542 911 3572 1714 1275 4257 1054 1267 4563 2198 3255 4585 4704 1686 2681 1873 2994 4726 1731 2986 4117 1170 2808 1943 2850 905 4774 1931 3841 246 2593 2502 543 2605 4403 1206 4702 2199...
output:
973970642
result:
ok 1 number(s): "973970642"
Test #17:
score: 0
Accepted
time: 7ms
memory: 4792kb
input:
5000 772 3375 4913 3401 4995 515 3179 2902 3284 475 3658 2590 3549 2308 910 2606 680 185 509 90 1924 4153 2011 4656 4000 68 3429 4147 4605 1481 965 4241 4995 2696 3135 12 4034 4002 3091 2838 57 1555 2835 602 4828 1229 4729 155 4702 3040 1057 1851 2025 3088 2678 4555 2252 1493 4086 2591 3781 1204 183...
output:
427070782
result:
ok 1 number(s): "427070782"
Test #18:
score: 0
Accepted
time: 7ms
memory: 4036kb
input:
5000 4445 91 4892 3144 2211 2563 2870 3754 550 4912 1989 1100 106 3681 1330 952 3652 920 1929 3103 3103 323 4418 3103 3632 4006 3103 1282 3103 1672 322 1734 3103 1780 325 3652 3103 4647 3652 1314 3652 81 746 168 1823 3247 1099 64 4697 2107 347 3176 4572 3200 204 4136 3103 1052 2771 1082 430 3103 310...
output:
984937631
result:
ok 1 number(s): "984937631"
Test #19:
score: 0
Accepted
time: 8ms
memory: 4048kb
input:
5000 2762 4174 3749 4061 2401 4137 3509 87 738 4912 2125 122 1629 92 329 2565 929 4966 1078 4233 466 2498 716 2596 3664 898 3320 2349 1865 4545 1642 3289 4958 843 3923 2840 4265 3954 425 1203 2640 596 3882 880 92 4141 1643 2079 3406 2296 3121 3219 1204 3547 3804 984 92 4250 4214 3202 2972 3278 3512 ...
output:
944816617
result:
ok 1 number(s): "944816617"
Test #20:
score: 0
Accepted
time: 9ms
memory: 4484kb
input:
5000 4113 1739 3973 1451 2460 3070 3293 445 1731 4615 1245 3345 2839 3050 977 3596 1370 4639 3160 2231 731 1137 2217 3625 2555 4018 4590 3946 2081 2436 4737 1996 574 3142 2885 3317 1422 4527 2342 2047 210 236 1155 3361 4920 4224 1265 2526 3303 2425 2327 1641 1892 3579 4439 2996 442 196 427 702 2307 ...
output:
257696103
result:
ok 1 number(s): "257696103"
Test #21:
score: 0
Accepted
time: 9ms
memory: 4360kb
input:
5000 3211 1670 1086 2203 2311 2995 1660 2918 4685 500 4437 2425 4941 4896 2697 2535 1051 510 3015 3300 190 1381 2074 2181 5000 3799 2638 2097 974 2152 3719 3341 1064 4568 2345 4712 3255 2205 90 2206 2929 465 2364 2069 295 1035 2506 3915 4129 718 4603 1390 256 2845 1600 3283 4420 3287 3388 4131 739 6...
output:
90790805
result:
ok 1 number(s): "90790805"
Test #22:
score: 0
Accepted
time: 9ms
memory: 4572kb
input:
5000 3950 571 1358 753 2584 2176 1982 934 2977 2775 4061 3191 3757 67 2787 4223 2512 1991 1077 2815 1394 3481 371 336 2282 4211 2175 1021 1806 4564 1920 601 3342 1526 3402 2419 310 231 3295 4403 4337 216 4068 3799 4728 4309 3703 4668 541 4204 4501 1916 132 831 793 2791 4188 4731 1485 4305 3968 2197 ...
output:
348148683
result:
ok 1 number(s): "348148683"
Test #23:
score: 0
Accepted
time: 6ms
memory: 4656kb
input:
5000 4686 4000 2056 3139 703 3076 4552 1909 2446 214 1454 923 717 187 851 3828 721 1436 1442 1907 513 547 161 4222 1388 4491 861 4494 983 4977 3741 3860 623 4069 3862 539 1957 4795 1157 4347 1202 1908 260 3767 3878 3611 4032 4218 984 2786 4163 3215 1347 4862 3118 2005 4171 1335 274 4756 959 3982 270...
output:
137895194
result:
ok 1 number(s): "137895194"
Test #24:
score: 0
Accepted
time: 487ms
memory: 82144kb
input:
200000 193646 193124 136401 140362 152430 149598 107317 106567 192382 192315 60375 61977 159553 160535 11641 11511 190147 189847 55014 52591 70317 88588 11641 25917 48335 45757 116921 124433 57211 50687 122916 122332 198934 198765 16631 11641 198103 198367 83133 68761 87932 69386 39246 38657 177413 ...
output:
727927914
result:
ok 1 number(s): "727927914"
Test #25:
score: 0
Accepted
time: 452ms
memory: 78232kb
input:
200000 12166 11726 137283 142820 31053 35541 106694 101141 26851 25452 56714 53513 110221 110912 163816 161984 95516 93488 113051 118110 62456 61874 16568 9043 183305 182485 1740 5440 35037 33177 125158 132799 68398 61536 141916 142669 104690 108054 7490 19341 63290 68761 44904 43782 76573 79270 154...
output:
483662812
result:
ok 1 number(s): "483662812"
Test #26:
score: 0
Accepted
time: 455ms
memory: 70752kb
input:
200000 121578 120778 166046 166804 63008 62707 172805 180182 121452 139614 186476 185972 139628 124358 80298 84225 157354 159700 149701 148093 127373 122225 144050 144025 47004 47069 176483 169839 99607 95182 1764 1602 79431 74006 175002 179584 56326 56144 179379 170975 54222 50474 85395 84148 65784...
output:
461047062
result:
ok 1 number(s): "461047062"
Test #27:
score: 0
Accepted
time: 468ms
memory: 58972kb
input:
200000 100775 100063 87081 108100 156436 177193 136419 136502 139323 139673 125338 124601 148748 151484 6706 1509 163197 173317 146956 147663 62587 62420 81191 81353 4474 6228 139615 139323 51121 51985 134049 131468 34899 37105 14703 8157 188866 188888 32458 33525 74150 68029 137091 137161 80703 807...
output:
323976684
result:
ok 1 number(s): "323976684"
Test #28:
score: 0
Accepted
time: 474ms
memory: 53700kb
input:
200000 75154 77487 74797 73738 91922 94229 71371 71042 112758 113514 83514 81684 77032 77997 141158 145688 24403 23868 168468 168980 109670 105380 100741 100810 75991 78681 3228 3208 195981 191953 105030 106739 118015 118706 65451 65639 33558 29789 88536 88054 49710 50037 70248 71371 148635 148363 2...
output:
731876547
result:
ok 1 number(s): "731876547"
Test #29:
score: 0
Accepted
time: 422ms
memory: 54608kb
input:
200000 130054 137125 114908 112689 30722 30316 67448 68098 170624 170271 182824 176800 108903 109437 186356 186394 59620 57261 101903 101154 27387 22793 2699 6573 1222 1453 182824 176963 99804 101903 182824 180038 59985 58789 101903 91549 49887 49522 155267 155107 83041 83324 34374 34913 195060 1921...
output:
553939859
result:
ok 1 number(s): "553939859"
Test #30:
score: 0
Accepted
time: 464ms
memory: 68524kb
input:
200000 4894 6412 53545 54035 140736 136599 124060 124370 171469 168053 23289 23894 96807 97678 95096 94433 140927 144000 110339 98460 185717 185849 182300 184326 87783 81857 63094 61735 106047 97160 89453 89552 58628 57920 196407 196040 139563 143609 49826 49878 61905 62598 196040 199845 88191 81119...
output:
500537103
result:
ok 1 number(s): "500537103"
Test #31:
score: 0
Accepted
time: 513ms
memory: 75248kb
input:
200000 100795 106977 86271 105796 145926 148854 178640 178182 6112 4817 55775 58052 13027 14571 127124 126379 103851 106050 131318 124208 68080 62774 41473 41924 87128 93531 26758 26803 97660 90205 179072 178640 124567 121774 48470 49694 162758 175257 16228 16207 114627 112472 8004 6214 58789 61707 ...
output:
611869539
result:
ok 1 number(s): "611869539"
Test #32:
score: 0
Accepted
time: 445ms
memory: 80688kb
input:
200000 144258 141041 93073 93160 105417 102924 8321 9035 182623 185868 46196 43971 52347 42632 182623 184969 69375 66549 182623 169919 52853 52535 149368 152025 2352 2356 123602 131028 183063 182623 177813 182623 50029 42593 141719 141963 85309 90867 117329 116147 74059 73804 134444 124516 102816 10...
output:
434720350
result:
ok 1 number(s): "434720350"
Test #33:
score: 0
Accepted
time: 500ms
memory: 87028kb
input:
200000 151689 138003 179765 113024 5801 27701 65969 193663 132677 83473 19409 110898 111101 146648 153845 41675 179244 181208 159170 41675 41675 131782 41675 156968 61313 43871 163483 59686 18972 175803 47468 24912 112068 103639 117244 41675 124400 5560 86058 93328 27819 147912 41675 177562 137345 1...
output:
694969257
result:
ok 1 number(s): "694969257"
Test #34:
score: 0
Accepted
time: 626ms
memory: 93652kb
input:
200000 129630 181282 112751 67798 92719 165324 108349 87950 18431 11840 87478 63835 79012 70121 28514 53132 61786 9873 136685 86715 121776 9397 181601 194414 159260 172551 6548 147570 159198 199950 88739 68208 77570 157998 38786 26167 46136 198855 33059 156449 11200 46835 104770 186167 23678 29667 1...
output:
903773595
result:
ok 1 number(s): "903773595"
Test #35:
score: 0
Accepted
time: 565ms
memory: 98084kb
input:
200000 118699 136408 17053 46361 37038 167068 123157 76040 56143 184706 196149 3987 89677 91756 24232 26908 115752 14628 64501 164190 92709 176309 138154 80618 130369 53312 164118 134823 54852 61337 57976 84207 133086 85576 102789 14578 112502 19956 130804 27897 156955 73854 192140 149302 91583 1493...
output:
151531259
result:
ok 1 number(s): "151531259"
Test #36:
score: 0
Accepted
time: 588ms
memory: 103464kb
input:
200000 173980 7891 88130 111730 198966 51703 140531 6174 95854 148987 127993 4468 31962 98444 129376 36332 92173 168662 11772 170597 105371 81842 141731 21913 93951 177228 27473 195489 103865 29472 113048 29240 91754 78199 162486 131228 81343 16925 63887 87959 37924 10213 36000 140391 146625 103762 ...
output:
147972383
result:
ok 1 number(s): "147972383"
Test #37:
score: 0
Accepted
time: 570ms
memory: 108380kb
input:
200000 97770 19875 29223 165934 182993 9628 108676 128716 34460 178839 52027 114763 126978 91049 38526 188293 10727 136637 93230 154363 75593 49771 15691 84647 31171 163308 5401 120509 163729 10736 67154 23878 96838 91654 112778 168655 126032 95125 138444 119576 83775 171297 186153 52398 106299 1247...
output:
591735912
result:
ok 1 number(s): "591735912"
Test #38:
score: 0
Accepted
time: 582ms
memory: 113532kb
input:
200000 75986 100005 17232 91894 120393 101065 180948 65437 133793 101336 31389 43095 122391 132549 16966 193965 24665 170134 124745 177925 170330 156646 94477 157154 190849 89357 46332 78982 90622 138103 166835 165736 192433 29453 157483 129126 83211 150070 124954 145345 140339 175748 91897 83125 19...
output:
991050818
result:
ok 1 number(s): "991050818"
Test #39:
score: 0
Accepted
time: 641ms
memory: 86516kb
input:
200000 32829 121233 29146 62140 158405 74698 185917 26733 163896 150236 145204 54213 2526 104991 37305 23594 157165 133687 108857 56391 146801 1947 72151 49147 86561 135448 12241 135880 191559 148214 85652 96094 178121 15128 183810 129508 195609 191507 21500 102757 68962 156731 154830 65808 144788 1...
output:
362050546
result:
ok 1 number(s): "362050546"
Test #40:
score: 0
Accepted
time: 619ms
memory: 89876kb
input:
200000 158678 56306 150217 38492 119262 8785 2420 2164 14836 6692 39442 166053 8195 8785 148729 199179 148687 124720 147547 95352 129284 110183 95818 133414 74970 84878 106604 135311 151236 8272 147534 196487 33322 70844 17474 162953 192834 150217 134287 150217 192552 11839 172854 169380 47852 11520...
output:
641283427
result:
ok 1 number(s): "641283427"
Test #41:
score: 0
Accepted
time: 666ms
memory: 95616kb
input:
200000 168742 110785 3016 108963 39711 132059 149669 71665 57403 7883 60071 101707 48208 188588 14665 75722 129805 17926 110511 48489 129276 110581 70407 55870 150963 183497 24929 137775 137255 79625 55771 190981 182922 164326 52691 38044 30928 137582 34586 30301 33072 194060 130981 72280 159219 417...
output:
440430277
result:
ok 1 number(s): "440430277"
Test #42:
score: 0
Accepted
time: 635ms
memory: 97348kb
input:
200000 51065 87259 80194 160352 87353 145155 161571 18352 105409 194959 193463 76990 158539 192211 129619 174564 125516 28414 175748 28144 64428 124171 96215 185077 58932 71516 26867 109640 27159 193057 85870 106422 191975 58828 128481 186326 41437 67261 107484 70677 21723 139575 158256 35170 179515...
output:
439078240
result:
ok 1 number(s): "439078240"
Test #43:
score: 0
Accepted
time: 720ms
memory: 106680kb
input:
200000 96987 94094 120906 91418 13164 166017 120954 13527 193912 20904 144661 112053 63214 3262 51288 27201 69777 123527 25889 153638 129853 61839 66218 44838 19214 13187 27957 67209 5802 136568 77933 137987 166848 22829 82927 18499 106883 122324 87110 17860 121569 166887 136252 154456 149005 112075...
output:
70916748
result:
ok 1 number(s): "70916748"
Test #44:
score: 0
Accepted
time: 687ms
memory: 98752kb
input:
200000 153443 142854 97331 146374 67670 84177 97823 40284 107785 25819 25486 6716 67384 62036 84830 104660 140050 58653 151899 156979 48929 12811 109552 19991 62547 59286 75910 172639 5076 56644 70860 198157 189147 49401 185216 135114 68314 171996 185243 105350 185761 101962 32069 199834 114040 1416...
output:
683287273
result:
ok 1 number(s): "683287273"
Test #45:
score: 0
Accepted
time: 223ms
memory: 111928kb
input:
200000 200000 199999 199999 199998 199998 199997 199997 199996 199996 199995 199995 199994 199994 199993 199993 199992 199992 199991 199991 199990 199990 199989 199989 199988 199988 199987 199987 199986 199986 199985 199985 199984 199984 199983 199983 199982 199982 199981 199981 199980 199980 199979...
output:
943946736
result:
ok 1 number(s): "943946736"
Test #46:
score: 0
Accepted
time: 186ms
memory: 113364kb
input:
200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
64266001
result:
ok 1 number(s): "64266001"
Extra Test:
score: 0
Extra Test Passed