結果
| 問題 | No.1288 yuki collection |
| ユーザー |
 37kt
|
| 提出日時 | 2024-04-03 13:00:01 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 2,387 ms / 5,000 ms |
| コード長 | 31,734 bytes |
| コンパイル時間 | 2,128 ms |
| コンパイル使用メモリ | 207,776 KB |
| 実行使用メモリ | 6,676 KB |
| 最終ジャッジ日時 | 2024-04-03 13:00:30 |
| 合計ジャッジ時間 | 28,821 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,676 KB |
| testcase_01 | AC | 1 ms
6,676 KB |
| testcase_02 | AC | 1 ms
6,676 KB |
| testcase_03 | AC | 1 ms
6,676 KB |
| testcase_04 | AC | 1 ms
6,676 KB |
| testcase_05 | AC | 1 ms
6,676 KB |
| testcase_06 | AC | 2 ms
6,676 KB |
| testcase_07 | AC | 1 ms
6,676 KB |
| testcase_08 | AC | 2 ms
6,676 KB |
| testcase_09 | AC | 1 ms
6,676 KB |
| testcase_10 | AC | 2 ms
6,676 KB |
| testcase_11 | AC | 1 ms
6,676 KB |
| testcase_12 | AC | 2 ms
6,676 KB |
| testcase_13 | AC | 693 ms
6,676 KB |
| testcase_14 | AC | 651 ms
6,676 KB |
| testcase_15 | AC | 473 ms
6,676 KB |
| testcase_16 | AC | 609 ms
6,676 KB |
| testcase_17 | AC | 730 ms
6,676 KB |
| testcase_18 | AC | 645 ms
6,676 KB |
| testcase_19 | AC | 601 ms
6,676 KB |
| testcase_20 | AC | 691 ms
6,676 KB |
| testcase_21 | AC | 412 ms
6,676 KB |
| testcase_22 | AC | 481 ms
6,676 KB |
| testcase_23 | AC | 501 ms
6,676 KB |
| testcase_24 | AC | 652 ms
6,676 KB |
| testcase_25 | AC | 644 ms
6,676 KB |
| testcase_26 | AC | 640 ms
6,676 KB |
| testcase_27 | AC | 2,387 ms
6,676 KB |
| testcase_28 | AC | 1,428 ms
6,676 KB |
| testcase_29 | AC | 356 ms
6,676 KB |
| testcase_30 | AC | 2,070 ms
6,676 KB |
| testcase_31 | AC | 1,823 ms
6,676 KB |
| testcase_32 | AC | 1,897 ms
6,676 KB |
| testcase_33 | AC | 639 ms
6,676 KB |
| testcase_34 | AC | 619 ms
6,676 KB |
| testcase_35 | AC | 646 ms
6,676 KB |
| testcase_36 | AC | 159 ms
6,676 KB |
| testcase_37 | AC | 482 ms
6,676 KB |
| testcase_38 | AC | 644 ms
6,676 KB |
| testcase_39 | AC | 664 ms
6,676 KB |
| testcase_40 | AC | 2,294 ms
6,676 KB |
| testcase_41 | AC | 1 ms
6,676 KB |
| testcase_42 | AC | 1 ms
6,676 KB |
コンパイルメッセージ
warning: unreachable expression
--> Main.rs:162:13
|
161 | exit(0);
| ------- any code following this expression is unreachable
162 | Ok(value)
| ^^^^^^^^^ unreachable expression
|
= note: `#[warn(unreachable_code)]` on by default
warning: unused variable: `c`
--> Main.rs:422:10
|
422 | let (c, f) = g.min_cost_flow(src, dst).unwrap();
| ^ help: if this is intentional, prefix it with an underscore: `_c`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `f`
--> Main.rs:422:13
|
422 | let (c, f) = g.min_cost_flow(src, dst).unwrap();
| ^ help: if this is intentional, prefix it with an underscore: `_f`
warning: variable does not need to be mutable
--> Main.rs:401:9
|
401 | let mut src = g.add_vertex();
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> Main.rs:402:9
|
402 | let mut dst = g.add_vertex();
| ----^^^
| |
| help: remove this `mut`
warning: 5 warnings emitted
ソースコード
// reference: https://misawa.github.io/others/flow/lets_use_capacity_scaling.html
pub use __cargo_equip::prelude::*;
use std::{cmp::Reverse, collections::BinaryHeap, process::exit};
const UNREACHABLE: i64 = std::i64::MAX;
const SCALING_FACTOR: i64 = 2;
#[derive(Debug, Clone, Copy)]
pub struct Edge {
pub from: usize,
pub to: usize,
pub lower: i64,
pub upper: i64,
pub cost: i64,
pub gain: i64,
pub flow: i64,
}
pub struct MinCostBFlow {
n: usize,
edges: Vec<Edge_>,
head: Vec<usize>,
next: Vec<usize>,
b: Vec<i64>,
farthest: i64,
potential: Vec<i64>,
dist: Vec<i64>,
parent: Vec<usize>,
pq: BinaryHeap<Reverse<(i64, usize)>>,
excess_vs: Vec<usize>,
deficit_vs: Vec<usize>,
}
impl MinCostBFlow {
pub fn new() -> Self {
Self {
n: 0,
edges: vec![],
head: vec![],
next: vec![],
b: vec![],
farthest: 0,
potential: vec![],
dist: vec![],
parent: vec![],
pq: Default::default(),
excess_vs: vec![],
deficit_vs: vec![],
}
}
pub fn add_vertex(&mut self) -> usize {
self.n += 1;
self.head.push(!0);
self.b.push(0);
self.n - 1
}
pub fn add_vertices(&mut self, size: usize) -> Vec<usize> {
self.n += size;
self.head.append(&mut vec![!0; size]);
self.b.append(&mut vec![0; size]);
(self.n - size..self.n).collect()
}
pub fn add_edge(&mut self, from: usize, to: usize, lower: i64, upper: i64, cost: i64) -> usize {
assert!(lower <= upper);
assert!(from < self.n);
assert!(to < self.n);
let m = self.edges.len();
self.next.push(self.head[from]);
self.head[from] = m;
self.next.push(self.head[to]);
self.head[to] = m + 1;
self.edges.push(Edge_ {
to,
cap: upper,
cost,
flow: 0,
});
self.edges.push(Edge_ {
to: from,
cap: -lower,
cost: -cost,
flow: 0,
});
m / 2
}
pub fn add_supply(&mut self, v: usize, amount: i64) {
self.b[v] += amount;
}
pub fn add_demand(&mut self, v: usize, amount: i64) {
self.b[v] -= amount;
}
pub fn get_edge(&self, e: usize) -> Edge {
assert!(e <= self.edges.len() / 2);
let e = e * 2;
Edge {
from: self.from(e),
to: self.to(e),
lower: self.lower(e),
upper: self.upper(e),
cost: self.cost(e),
gain: self.gain(e),
flow: self.flow(e),
}
}
pub fn get_edges(&self) -> Vec<Edge> {
(0..self.edges.len() / 2)
.map(|e| self.get_edge(e))
.collect()
}
pub fn min_cost_b_flow(&mut self) -> Result<i64, i64> {
self.potential.resize(self.n, 0);
for u in 0..self.n {
let mut e = self.head[u];
while e != !0 {
let rcap = self.residual_cap(e);
if rcap < 0 {
self.push(e, rcap);
self.b[u] -= rcap;
let v = self.to(e);
self.b[v] += rcap;
}
e = self.next[e];
}
}
let mut inf_flow = 1;
for e in 0..self.edges.len() {
inf_flow = inf_flow.max(self.residual_cap(e));
}
let mut delta = 1;
while delta * SCALING_FACTOR <= inf_flow {
delta *= SCALING_FACTOR;
}
while delta > 0 {
self.saturate_negative(delta);
while self.dual(delta) {
self.primal(delta);
}
delta /= SCALING_FACTOR;
}
let mut value = 0;
for Edge_ { flow, cost, .. } in &self.edges {
value += flow * cost;
}
value /= 2;
if self.excess_vs.is_empty() && self.deficit_vs.is_empty() {
println!("{}", -value);
exit(0);
Ok(value)
} else {
Err(value)
}
}
/// (コスト, 流量)
pub fn min_cost_flow(&mut self, s: usize, t: usize) -> Result<(i64, i64), (i64, i64)> {
assert!(s != t);
let mut inf_flow = self.b[s].abs();
let mut e = self.head[s];
while e != !0 {
inf_flow += 0.max(self.edges[e].cap);
e = self.next[e];
}
self.add_edge(t, s, 0, inf_flow, 0);
if let Err(circulation_value) = self.min_cost_b_flow() {
self.head[s] = self.next[s];
self.head[t] = self.next[t];
self.edges.pop();
self.edges.pop();
return Err((circulation_value, 0));
}
let mut inf_flow = self.b[s].abs();
let mut e = self.head[s];
while e != !0 {
inf_flow += self.residual_cap(e);
e = self.next[e];
}
self.b[s] += inf_flow;
self.b[t] -= inf_flow;
let mf_value = match self.min_cost_b_flow() {
Ok(v) => v,
Err(v) => v,
};
self.b[s] -= inf_flow;
self.b[t] += inf_flow;
self.head[s] = self.next[s];
self.head[t] = self.next[t];
self.edges.pop();
self.edges.pop();
Ok((mf_value, self.b[t]))
}
pub fn get_result_value_i128(&mut self) -> i128 {
let mut value = 0;
for e in &self.edges {
value += e.flow as i128 * e.cost as i128;
}
value / 2
}
pub fn get_potential(&mut self) -> Vec<i64> {
self.potential = vec![0; self.n];
for _ in 0..self.n {
for e in 0..self.edges.len() {
if self.residual_cap(e) > 0 {
let to = self.to(e);
self.potential[to] =
self.potential[to].min(self.potential[self.from(e)] + self.cost(e));
}
}
}
self.potential.clone()
}
fn from(&self, e: usize) -> usize {
self.edges[e ^ 1].to
}
fn to(&self, e: usize) -> usize {
self.edges[e].to
}
fn flow(&self, e: usize) -> i64 {
self.edges[e].flow
}
fn lower(&self, e: usize) -> i64 {
-self.edges[e ^ 1].cap
}
fn upper(&self, e: usize) -> i64 {
self.edges[e].cap
}
fn cost(&self, e: usize) -> i64 {
self.edges[e].cost
}
fn gain(&self, e: usize) -> i64 {
-self.edges[e].cost
}
fn push(&mut self, e: usize, amount: i64) {
self.edges[e].flow += amount;
self.edges[e ^ 1].flow -= amount;
}
fn residual_cost(&self, e: usize) -> i64 {
self.cost(e) + self.potential[self.from(e)] - self.potential[self.to(e)]
}
fn residual_cap(&self, e: usize) -> i64 {
self.edges[e].cap - self.edges[e].flow
}
fn dual(&mut self, delta: i64) -> bool {
self.dist = vec![UNREACHABLE; self.n];
self.parent = vec![!0; self.n];
// self.excess_vs.retain(|v| self.b[*v] >= delta);
for i in (0..self.excess_vs.len()).rev() {
if self.b[self.excess_vs[i]] < delta {
self.excess_vs.swap_remove(i);
}
}
// self.deficit_vs.retain(|v| self.b[*v] <= -delta);
for i in (0..self.deficit_vs.len()).rev() {
if self.b[self.deficit_vs[i]] > -delta {
self.deficit_vs.swap_remove(i);
}
}
for &v in &self.excess_vs {
self.dist[v] = 0;
self.pq.push(Reverse((0, v)));
}
self.farthest = 0;
let mut deficit_count = 0;
while let Some(Reverse((d, u))) = self.pq.pop() {
if self.dist[u] < d {
continue;
}
self.farthest = d;
if self.b[u] <= -delta {
deficit_count += 1;
}
if deficit_count >= self.deficit_vs.len() {
break;
}
let mut e = self.head[u];
while e != !0 {
if self.residual_cap(e) >= delta {
let v = self.to(e);
let new_dist = d + self.residual_cost(e);
if self.dist[v] > new_dist {
self.dist[v] = new_dist;
self.pq.push(Reverse((new_dist, v)));
self.parent[v] = e;
}
}
e = self.next[e];
}
}
self.pq.clear();
for v in 0..self.n {
self.potential[v] += self.dist[v].min(self.farthest);
}
deficit_count > 0
}
fn primal(&mut self, delta: i64) {
for i in 0..self.deficit_vs.len() {
let t = self.deficit_vs[i];
if self.dist[t] > self.farthest {
continue;
}
let mut f = -self.b[t];
let mut v = t;
while self.parent[v] != !0 && f >= delta {
f = f.min(self.residual_cap(self.parent[v]));
v = self.from(self.parent[v]);
}
f = f.min(self.b[v]);
if f < delta {
continue;
}
v = t;
while self.parent[v] != !0 {
self.push(self.parent[v], f);
let u = self.from(self.parent[v]);
self.parent[v] = !0;
v = u;
}
self.b[t] += f;
self.b[v] -= f;
}
}
fn saturate_negative(&mut self, delta: i64) {
self.excess_vs.clear();
self.deficit_vs.clear();
for u in 0..self.n {
let mut e = self.head[u];
while e != !0 {
let rcap = self.residual_cap(e);
let rcost = self.residual_cost(e);
if rcost < 0 && rcap >= delta {
self.push(e, rcap);
self.b[u] -= rcap;
let v = self.to(e);
self.b[v] += rcap;
}
e = self.next[e];
}
}
for v in 0..self.n {
if self.b[v] > 0 {
self.excess_vs.push(v);
} else if self.b[v] < 0 {
self.deficit_vs.push(v);
}
}
}
}
struct Edge_ {
to: usize,
cap: i64,
cost: i64,
flow: i64,
}
#[allow(unused_imports)]
use proconio::{
input,
marker::{Bytes, Chars, Usize1},
};
fn main() {
input! {
n: usize,
s: Bytes,
v: [i64; n],
}
let mut g = MinCostBFlow::new();
let mut vs = vec![vec![0; 5]; n + 1];
let mut src = g.add_vertex();
let mut dst = g.add_vertex();
for i in 0..=n {
for j in 0..5 {
vs[i][j] = g.add_vertex();
}
}
for i in 0..n {
let t = match s[i] {
b'y' => 0,
b'u' => 1,
b'k' => 2,
_ => 3,
};
g.add_edge(vs[i][t], vs[i + 1][t + 1], 0, 1, -v[i]);
for j in 0..5 {
g.add_edge(vs[i][j], vs[i + 1][j], 0, 500, 0);
}
}
g.add_edge(src, vs[0][0], 0, 500, 0);
g.add_edge(vs[n][4], dst, 0, 500, 0);
let (c, f) = g.min_cost_flow(src, dst).unwrap();
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::__lazy_static_1_4_0`
/// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
///
/// # Procedural macros
///
/// - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
///
/// # License and Copyright Notices
///
/// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// Copyright (c) 2010 The Rust Project Developers
///
/// Permission is hereby granted, free of charge, to any
/// person obtaining a copy of this software and associated
/// documentation files (the "Software"), to deal in the
/// Software without restriction, including without
/// limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software
/// is furnished to do so, subject to the following
/// conditions:
///
/// The above copyright notice and this permission notice
/// shall be included in all copies or substantial portions
/// of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
/// ```
///
/// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// The MIT License
/// Copyright 2019 (C) statiolake <statiolake@gmail.com>
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of
/// this software and associated documentation files (the "Software"), to deal in
/// the Software without restriction, including without limitation the rights to
/// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software is furnished to do so,
/// subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all
/// copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
/// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
/// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
/// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
/// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
///
/// Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019. The
/// original macro is licensed under BSD 3-clause license.
///
/// Redistribution and use in source and binary forms, with or without
/// modification, are permitted provided that the following conditions are met:
///
/// 1. Redistributions of source code must retain the above copyright notice, this
/// list of conditions and the following disclaimer.
///
/// 2. Redistributions in binary form must reproduce the above copyright notice,
/// this list of conditions and the following disclaimer in the documentation
/// and/or other materials provided with the distribution.
///
/// 3. Neither the name of the copyright holder nor the names of its contributors
/// may be used to endorse or promote products derived from this software
/// without specific prior written permission.
///
/// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
/// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
/// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
/// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
/// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
/// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
/// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
/// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
/// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
/// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
/// ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::__Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input. ","This is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
pub mod __proconio_derive_0_2_1 {pub use crate::__cargo_equip::macros::__proconio_derive_0_2_1::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
}
pub(crate) mod macros {
pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};}
pub mod __proconio_derive_0_2_1 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_2_1_fastout as fastout};}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}
mod preludes {
pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__lazy_static_1_4_0 as lazy_static,__proconio_derive_0_2_1 as proconio_derive};}
pub mod __proconio_derive_0_2_1 {}
}
}