QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731270 | #9564. Hey, Have You Seen My Kangaroo? | ucup-team296 | AC ✓ | 1719ms | 37456kb | Rust | 71.3kb | 2024-11-10 01:26:33 | 2024-11-10 01:26:33 |
Judging History
answer
// https://contest.ucup.ac/contest/1828/problem/9564
pub mod solution {
//{"name":"A. Hey, Have You Seen My Kangaroo?","group":"Universal Cup - The 3rd Universal Cup. Stage 16: Nanjing","url":"https://contest.ucup.ac/contest/1828/problem/9564","interactive":false,"timeLimit":1000,"tests":[{"input":"3 3 6\nULDDRR\n010\n111\n010\n","output":"-1\n4\n2\n1\n0\n0\n0\n0\n0\n"},{"input":"3 3 6\nULDDRR\n010\n111\n011\n","output":"7\n4\n2\n1\n1\n0\n0\n0\n0\n"},{"input":"1 5 1\nR\n11111\n","output":"4\n3\n2\n1\n0\n"}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"AHeyHaveYouSeenMyKangaroo"}}}
use crate::algo_lib::collections::bit_set::BitSet;
use crate::algo_lib::collections::fx_hash_map::FxHashMap;
use crate::algo_lib::collections::iter_ext::collect::IterCollect;
use crate::algo_lib::collections::md_arr::arr2d::Arr2dRead;
use crate::algo_lib::collections::min_max::MinimMaxim;
use crate::algo_lib::collections::slice_ext::indices::Indices;
use crate::algo_lib::graph::edges::edge::Edge;
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::Callable;
use crate::algo_lib::misc::recursive_function::RecursiveFunction;
use crate::algo_lib::misc::test_type::TaskType;
use crate::algo_lib::misc::test_type::TestType;
use crate::algo_lib::string::str::StrReader;
use std::cmp::Reverse;
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
let n = input.read_size();
let m = input.read_size();
let k = input.read_size();
let s = input.read_str();
let a = input.read_char_table(n, m);
let mut graph = Graph::new(n * m);
let mut is_root = BitSet::new(n * m);
let mut x = vec![None; n * m];
let mv = |r: usize, c: usize, cc: u8| -> (usize, usize) {
match cc {
b'U' => {
if r > 0 && a[(r - 1, c)] == b'1' {
return (r - 1, c);
}
}
b'D' => {
if r + 1 < n && a[(r + 1, c)] == b'1' {
return (r + 1, c);
}
}
b'L' => {
if c > 0 && a[(r, c - 1)] == b'1' {
return (r, c - 1);
}
}
b'R' => {
if c + 1 < m && a[(r, c + 1)] == b'1' {
return (r, c + 1);
}
}
_ => unreachable!(),
}
(r, c)
};
for i in 0..n {
for j in 0..m {
if a[(i, j)] == b'0' {
continue;
}
let mut r = i;
let mut c = j;
for cc in s.iter() {
(r, c) = mv(r, c, cc);
}
x[i * m + j] = Some(r * m + c);
}
}
let mut done = vec![0; n * m];
let mut root_shift = (0..n * m).collect_vec();
for i in 0..n * m {
if done[i] == 2 || x[i].is_none() {
continue;
}
let mut cur = i;
while done[cur] == 0 {
done[cur] = 1;
cur = x[cur].unwrap();
}
while done[cur] == 1 {
is_root.set(cur);
done[cur] = 2;
root_shift[x[cur].unwrap()] = cur;
cur = x[cur].unwrap();
}
cur = i;
while done[cur] == 1 {
done[cur] = 2;
cur = x[cur].unwrap();
}
}
for i in 0..n * m {
if let Some(to) = x[i] {
if !is_root[i] {
graph.add_edge(Edge::new(root_shift[to], i));
}
}
}
let mut joins = Vec::new();
let mut ans = Vec::with_capacity(n * m);
for i in is_root.iter() {
let mut rec = RecursiveFunction::new(|rec, vert: usize| -> usize {
let mut lens = Vec::new();
let mut pos = Vec::new();
for e in &graph[vert] {
lens.push(rec.call(e.to()) + 1);
pos.push((e.to() / m, e.to() % m));
}
if is_root[vert] {
lens.push(usize::MAX);
pos.push((vert / m, vert % m));
}
let mut good = BitSet::new(pos.len());
good.fill(true);
for i in 0..k {
let mut seen = FxHashMap::<_, usize>::default();
for j in pos.indices() {
if !good[j] {
continue;
}
pos[j] = mv(pos[j].0, pos[j].1, s[i]);
if let Some(&o) = seen.get(&pos[j]) {
for x in 0..lens[o].min(lens[j]) {
joins.push(i + 1 + x * k);
}
let cand = lens[j];
lens[o].maxim(cand);
good.unset(j);
} else {
seen.insert(pos[j], j);
}
}
}
lens.get(0).copied().unwrap_or(0)
});
rec.call(i);
ans.push(None);
}
ans.pop();
joins.sort_by_key(|&x| Reverse(x));
ans.extend(joins.into_iter().map(Some));
ans.resize(n * m, Some(0));
out.print_per_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 bit_set {
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use crate::algo_lib::numbers::num_traits::bit_ops::BitOps;
use std::ops::BitAndAssign;
use std::ops::BitOrAssign;
use std::ops::Index;
use std::ops::ShlAssign;
use std::ops::ShrAssign;
const TRUE: bool = true;
const FALSE: bool = false;
#[derive(Clone, Eq, PartialEq, Hash)]
pub struct BitSet {
data: Vec<u64>,
len: usize,
}
impl BitSet {
pub fn new(len: usize) -> Self {
let data_len = if len == 0 {
0
} else {
Self::index(len - 1) + 1
};
Self {
data: vec![0; data_len],
len,
}
}
pub fn from_slice(len: usize, set: &[usize]) -> Self {
let mut res = Self::new(len);
for &i in set {
res.set(i);
}
res
}
pub fn set(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].set_bit(at & 63);
}
pub fn unset(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].unset_bit(at & 63);
}
pub fn change(&mut self, at: usize, value: bool) {
if value {
self.set(at);
} else {
self.unset(at);
}
}
pub fn flip(&mut self, at: usize) {
self.change(at, !self[at]);
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.len
}
pub fn fill(&mut self, value: bool) {
// 1.43
self.data.legacy_fill(if value { std::u64::MAX } else { 0 });
if value {
self.fix_last();
}
}
pub fn is_superset(&self, other: &Self) -> bool {
assert_eq!(self.len, other.len);
for i in 0..self.data.len() {
if self.data[i] & other.data[i] != other.data[i] {
return false;
}
}
true
}
pub fn is_subset(&self, other: &Self) -> bool {
other.is_superset(self)
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.into_iter()
}
fn index(at: usize) -> usize {
at >> 6
}
pub fn count_ones(&self) -> usize {
self.data.iter().map(|x| x.count_ones() as usize).sum()
}
fn fix_last(&mut self) {
if self.len & 63 != 0 {
let mask = (1 << (self.len & 63)) - 1;
*self.data.last_mut().unwrap() &= mask;
}
}
}
pub struct BitSetIter<'s> {
at: usize,
inside: usize,
set: &'s BitSet,
}
impl<'s> Iterator for BitSetIter<'s> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.at < self.set.data.len()
&& (self.inside == 64 || (self.set.data[self.at] >> self.inside) == 0)
{
self.at += 1;
self.inside = 0;
}
if self.at == self.set.data.len() {
None
} else {
while !self.set.data[self.at].is_set(self.inside) {
self.inside += 1;
}
let res = self.at * 64 + self.inside;
if res < self.set.len {
self.inside += 1;
Some(res)
} else {
None
}
}
}
}
impl<'a> IntoIterator for &'a BitSet {
type Item = usize;
type IntoIter = BitSetIter<'a>;
fn into_iter(self) -> Self::IntoIter {
BitSetIter {
at: 0,
inside: 0,
set: self,
}
}
}
impl BitOrAssign<&BitSet> for BitSet {
fn bitor_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i |= j;
}
}
}
impl BitAndAssign<&BitSet> for BitSet {
fn bitand_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i &= j;
}
}
}
impl ShlAssign<usize> for BitSet {
fn shl_assign(&mut self, rhs: usize) {
if rhs == 0 {
return;
}
let small_shift = rhs & 63;
if small_shift != 0 {
let mut carry = 0;
for i in 0..self.data.len() {
let new_carry = self.data[i] >> (64 - small_shift);
self.data[i] <<= small_shift;
self.data[i] |= carry;
carry = new_carry;
}
}
let big_shift = rhs >> 6;
if big_shift != 0 {
self.data.rotate_right(big_shift);
self.data[..big_shift].fill(0);
}
self.fix_last();
}
}
impl ShrAssign<usize> for BitSet {
fn shr_assign(&mut self, rhs: usize) {
if rhs == 0 {
return;
}
let small_shift = rhs & 63;
if small_shift != 0 {
let mut carry = 0;
for i in (0..self.data.len()).rev() {
let new_carry = self.data[i] << (64 - small_shift);
self.data[i] >>= small_shift;
self.data[i] |= carry;
carry = new_carry;
}
}
let big_shift = rhs >> 6;
if big_shift != 0 {
self.data.rotate_left(big_shift);
let from = self.data.len() - big_shift;
self.data[from..].fill(0);
}
}
}
impl Index<usize> for BitSet {
type Output = bool;
fn index(&self, at: usize) -> &Self::Output {
assert!(at < self.len);
if self.data[Self::index(at)].is_set(at & 63) {
&TRUE
} else {
&FALSE
}
}
}
impl From<Vec<bool>> for BitSet {
fn from(data: Vec<bool>) -> Self {
let mut res = Self::new(data.len());
for (i, &value) in data.iter().enumerate() {
res.change(i, value);
}
res
}
}
}
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::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 0..self.id.len() {
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 md_arr {
pub mod arr2d {
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
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 std::mem::MaybeUninit;
use std::ops::Index;
use std::ops::IndexMut;
use std::ops::Range;
use std::slice::Iter;
use std::vec::IntoIter;
#[derive(Clone, Eq, PartialEq, Default)]
pub struct Arr2d<T> {
d1: usize,
d2: usize,
data: Vec<T>,
}
impl<T: Clone> Arr2d<T> {
pub fn new(d1: usize, d2: usize, value: T) -> Self {
Self {
d1,
d2,
data: vec![value; d1 * d2],
}
}
}
impl<T> Arr2d<T> {
pub fn generate<F>(d1: usize, d2: usize, mut gen: F) -> Self
where
F: FnMut(usize, usize) -> T,
{
let mut data = Vec::with_capacity(d1 * d2);
for i in 0usize..d1 {
for j in 0usize..d2 {
data.push(gen(i, j));
}
}
Self { d1, d2, data }
}
pub fn d1(&self) -> usize {
self.d1
}
pub fn d2(&self) -> usize {
self.d2
}
pub fn iter(&self) -> Iter<'_, T> {
self.data.iter()
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
self.data.iter_mut()
}
pub fn row(&self, row: usize) -> impl Iterator<Item = &T> {
assert!(row < self.d1);
self.data.iter().skip(row * self.d2).take(self.d2)
}
pub fn row_mut(&mut self, row: usize) -> impl Iterator<Item = &mut T> {
assert!(row < self.d1);
self.data.iter_mut().skip(row * self.d2).take(self.d2)
}
pub fn column(&self, col: usize) -> impl Iterator<Item = &T> {
assert!(col < self.d2);
self.data.iter().skip(col).step_by(self.d2)
}
pub fn column_mut(&mut self, col: usize) -> impl Iterator<Item = &mut T> {
assert!(col < self.d2);
self.data.iter_mut().skip(col).step_by(self.d2)
}
pub fn swap(&mut self, r1: usize, c1: usize, r2: usize, c2: usize) {
assert!(r1 < self.d1);
assert!(r2 < self.d1);
assert!(c1 < self.d2);
assert!(c2 < self.d2);
self.data.swap(r1 * self.d2 + c1, r2 * self.d2 + c2);
}
pub fn rows(&self) -> Range<usize> {
0..self.d1
}
pub fn cols(&self) -> Range<usize> {
0..self.d2
}
pub fn swap_rows(&mut self, r1: usize, r2: usize) {
assert!(r1 < self.d1);
assert!(r2 < self.d1);
if r1 == r2 {
return;
}
let (r1, r2) = (r1.min(r2), r1.max(r2));
let (head, tail) = self.data.split_at_mut(r2 * self.d2);
head[r1 * self.d2..(r1 + 1) * self.d2].swap_with_slice(&mut tail[..self.d2]);
}
pub fn rotate_clockwise(self) -> Self {
unsafe {
let d1 = self.d1;
let d2 = self.d2;
let mut res = MaybeUninit::new(Vec::with_capacity(d1 * d2));
(*res.as_mut_ptr()).set_len(d1 * d2);
for (id, element) in self.into_iter().enumerate() {
let (i, j) = (id / d2, id % d2);
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(j * d1 + d1 - i - 1).write(element);
}
Self {
d1: d2,
d2: d1,
data: res.assume_init(),
}
}
}
pub fn rotate_counterclockwise(self) -> Self {
unsafe {
let d1 = self.d1;
let d2 = self.d2;
let mut res = MaybeUninit::new(Vec::with_capacity(d1 * d2));
(*res.as_mut_ptr()).set_len(d1 * d2);
for (id, element) in self.into_iter().enumerate() {
let (i, j) = (id / d2, id % d2);
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add((d2 - j - 1) * d1 + i).write(element);
}
Self {
d1: d2,
d2: d1,
data: res.assume_init(),
}
}
}
}
impl<T: Clone> Arr2d<T> {
pub fn fill(&mut self, elem: T) {
self.data.legacy_fill(elem);
}
pub fn transpose(&self) -> Self {
Self::generate(self.d2, self.d1, |i, j| self[(j, i)].clone())
}
}
impl<T> Index<(usize, usize)> for Arr2d<T> {
type Output = T;
fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
assert!(row < self.d1);
assert!(col < self.d2);
&self.data[self.d2 * row + col]
}
}
impl<T> Index<usize> for Arr2d<T> {
type Output = [T];
fn index(&self, index: usize) -> &Self::Output {
&self.data[self.d2 * index..self.d2 * (index + 1)]
}
}
impl<T> IndexMut<(usize, usize)> for Arr2d<T> {
fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut T {
assert!(row < self.d1);
assert!(col < self.d2);
&mut self.data[self.d2 * row + col]
}
}
impl<T> IndexMut<usize> for Arr2d<T> {
fn index_mut(&mut self, index: usize) -> &mut [T] {
&mut self.data[self.d2 * index..self.d2 * (index + 1)]
}
}
impl<T> AsRef<Vec<T>> for Arr2d<T> {
fn as_ref(&self) -> &Vec<T> {
&self.data
}
}
impl<T> AsMut<Vec<T>> for Arr2d<T> {
fn as_mut(&mut self) -> &mut Vec<T> {
&mut self.data
}
}
impl<T: Writable> Writable for Arr2d<T> {
fn write(&self, output: &mut Output) {
let mut at = 0usize;
for i in 0usize..self.d1 {
if i != 0 {
output.put(b'\n');
}
for j in 0usize..self.d2 {
if j != 0 {
output.put(b' ');
}
self.data[at].write(output);
at += 1;
}
}
}
}
impl<T> IntoIterator for Arr2d<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
self.data.into_iter()
}
}
impl<'a, T> IntoIterator for &'a Arr2d<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub trait Arr2dRead {
fn read_table<T: Readable>(&mut self, d1: usize, d2: usize) -> Arr2d<T>;
fn read_int_table(&mut self, d1: usize, d2: usize) -> Arr2d<i32>;
fn read_long_table(&mut self, d1: usize, d2: usize) -> Arr2d<i64>;
fn read_size_table(&mut self, d1: usize, d2: usize) -> Arr2d<usize>;
fn read_char_table(&mut self, d1: usize, d2: usize) -> Arr2d<u8>;
}
impl Arr2dRead for Input<'_> {
fn read_table<T: Readable>(&mut self, d1: usize, d2: usize) -> Arr2d<T> {
Arr2d::generate(d1, d2, |_, _| self.read())
}
fn read_int_table(&mut self, d1: usize, d2: usize) -> Arr2d<i32> {
self.read_table(d1, d2)
}
fn read_long_table(&mut self, d1: usize, d2: usize) -> Arr2d<i64> {
self.read_table(d1, d2)
}
fn read_size_table(&mut self, d1: usize, d2: usize) -> Arr2d<usize> {
self.read_table(d1, d2)
}
fn read_char_table(&mut self, d1: usize, d2: usize) -> Arr2d<u8> {
self.read_table(d1, d2)
}
}
pub trait Arr2dCharWrite {
fn print_table(&mut self, table: &Arr2d<u8>);
}
impl Arr2dCharWrite for Output<'_> {
fn print_table(&mut self, table: &Arr2d<u8>) {
let mut at = 0usize;
for _ in 0..table.d1 {
for _ in 0..table.d2 {
self.put(table.data[at]);
at += 1;
}
self.put(b'\n');
}
self.maybe_flush();
}
}
impl<T: Readable> Readable for Arr2d<T> {
fn read(input: &mut Input) -> Self {
let d1 = input.read();
let d2 = input.read();
input.read_table(d1, d2)
}
}
}
}
pub mod min_max {
pub trait MinimMaxim<Rhs = Self>: PartialOrd + Sized {
fn minim(&mut self, other: Rhs) -> bool;
fn maxim(&mut self, other: Rhs) -> bool;
}
impl<T: PartialOrd> MinimMaxim for T {
fn minim(&mut self, other: Self) -> bool {
if other < *self {
*self = other;
true
} else {
false
}
}
fn maxim(&mut self, other: Self) -> bool {
if other > *self {
*self = other;
true
} else {
false
}
}
}
impl<T: PartialOrd> MinimMaxim<T> for Option<T> {
fn minim(&mut self, other: T) -> bool {
match self {
None => {
*self = Some(other);
true
}
Some(v) => v.minim(other),
}
}
fn maxim(&mut self, other: T) -> bool {
match self {
None => {
*self = Some(other);
true
}
Some(v) => v.maxim(other),
}
}
}
}
pub mod slice_ext {
pub mod backward {
use std::ops::Index;
use std::ops::IndexMut;
pub struct Back(pub usize);
impl<T> Index<Back> for [T] {
type Output = T;
fn index(&self, index: Back) -> &Self::Output {
&self[self.len() - index.0 - 1]
}
}
impl<T> IndexMut<Back> for [T] {
fn index_mut(&mut self, index: Back) -> &mut Self::Output {
&mut self[self.len() - index.0 - 1]
}
}
impl<T> Index<Back> for Vec<T> {
type Output = T;
fn index(&self, index: Back) -> &Self::Output {
self.as_slice().index(index)
}
}
impl<T> IndexMut<Back> for Vec<T> {
fn index_mut(&mut self, index: Back) -> &mut Self::Output {
self.as_mut_slice().index_mut(index)
}
}
}
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 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 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;
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)
}
}
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: Option<usize>) {
self.precision = precision;
}
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 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 numbers {
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 bit_ops {
use crate::algo_lib::numbers::num_traits::algebra::One;
use crate::algo_lib::numbers::num_traits::algebra::Zero;
use std::ops::BitAnd;
use std::ops::BitAndAssign;
use std::ops::BitOr;
use std::ops::BitOrAssign;
use std::ops::BitXor;
use std::ops::BitXorAssign;
use std::ops::Not;
use std::ops::RangeInclusive;
use std::ops::Shl;
use std::ops::Sub;
use std::ops::ShlAssign;
use std::ops::Shr;
use std::ops::ShrAssign;
pub trait BitOps:
Copy
+ BitAnd<Output = Self>
+ BitAndAssign
+ BitOr<Output = Self>
+ BitOrAssign
+ BitXor<Output = Self>
+ BitXorAssign
+ Not<Output = Self>
+ Shl<usize, Output = Self>
+ ShlAssign<usize>
+ Shr<usize, Output = Self>
+ ShrAssign<usize>
+ Zero
+ One
+ PartialEq
{
fn bit(at: usize) -> Self {
Self::one() << at
}
fn is_set(&self, at: usize) -> bool {
(*self >> at & Self::one()) == Self::one()
}
fn set_bit(&mut self, at: usize) {
*self |= Self::bit(at)
}
fn unset_bit(&mut self, at: usize) {
*self &= !Self::bit(at)
}
#[must_use]
fn with_bit(mut self, at: usize) -> Self {
self.set_bit(at);
self
}
#[must_use]
fn without_bit(mut self, at: usize) -> Self {
self.unset_bit(at);
self
}
fn flip_bit(&mut self, at: usize) {
*self ^= Self::bit(at)
}
#[must_use]
fn flipped_bit(mut self, at: usize) -> Self {
self.flip_bit(at);
self
}
fn all_bits(n: usize) -> Self {
let mut res = Self::zero();
for i in 0..n {
res.set_bit(i);
}
res
}
fn iter_all(n: usize) -> RangeInclusive<Self> {
Self::zero()..=Self::all_bits(n)
}
}
pub struct BitIter<T> {
cur: T,
all: T,
ended: bool,
}
impl<T: Copy> BitIter<T> {
pub fn new(all: T) -> Self {
Self {
cur: all,
all,
ended: false,
}
}
}
impl<T: BitOps + Sub<Output = T>> Iterator for BitIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.ended {
return None;
}
let res = self.cur;
if self.cur == T::zero() {
self.ended = true;
} else {
self.cur = (self.cur - T::one()) & self.all;
}
Some(res)
}
}
impl<
T: Copy
+ BitAnd<Output = Self>
+ BitAndAssign
+ BitOr<Output = Self>
+ BitOrAssign
+ BitXor<Output = Self>
+ BitXorAssign
+ Not<Output = Self>
+ Shl<usize, Output = Self>
+ ShlAssign<usize>
+ Shr<usize, Output = Self>
+ ShrAssign<usize>
+ One
+ Zero
+ PartialEq,
> BitOps for T
{
}
pub trait Bits: BitOps {
fn bits() -> u32;
}
macro_rules! bits_integer_impl {
($($t: ident $bits: expr),+) => {$(
impl Bits for $t {
fn bits() -> u32 {
$bits
}
}
)+};
}
bits_integer_impl!(i128 128, i64 64, i32 32, i16 16, i8 8, isize 64, u128 128, u64 64, u32 32, u16 16, u8 8, usize 64);
}
pub mod invertible {
pub trait Invertible {
type Output;
fn inv(&self) -> Option<Self::Output>;
}
}
}
}
pub mod string {
pub mod str {
use crate::algo_lib::collections::iter_ext::collect::IterCollect;
use crate::algo_lib::collections::slice_ext::backward::Back;
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 std::cmp::Ordering;
use std::fmt::Debug;
use std::fmt::Display;
use std::fmt::Formatter;
use std::hash::Hash;
use std::hash::Hasher;
use std::iter::Copied;
use std::iter::FromIterator;
use std::marker::PhantomData;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Deref;
use std::ops::DerefMut;
use std::ops::Index;
use std::ops::IndexMut;
use std::ops::RangeBounds;
use std::slice::Iter;
use std::slice::IterMut;
use std::slice::SliceIndex;
use std::str::FromStr;
use std::vec::IntoIter;
pub enum Str<'s> {
Extendable(Vec<u8>, PhantomData<&'s [u8]>),
Owned(Box<[u8]>, PhantomData<&'s [u8]>),
Ref(&'s [u8]),
}
impl<'s> Str<'s> {
pub fn substr(&self, range: impl RangeBounds<usize>) -> Str {
let from = match range.start_bound() {
std::ops::Bound::Included(&i) => i,
std::ops::Bound::Excluded(&i) => i + 1,
std::ops::Bound::Unbounded => 0,
};
let to = match range.end_bound() {
std::ops::Bound::Included(&i) => i + 1,
std::ops::Bound::Excluded(&i) => i,
std::ops::Bound::Unbounded => self.len(),
};
Str::from(&self[from..to])
}
}
impl Default for Str<'static> {
fn default() -> Self {
Self::new()
}
}
impl Str<'static> {
pub fn new() -> Self {
Str::Extendable(Vec::new(), PhantomData)
}
pub fn with_capacity(cap: usize) -> Self {
Str::Extendable(Vec::with_capacity(cap), PhantomData)
}
}
impl<'s> Str<'s> {
pub fn push(&mut self, c: u8) {
self.transform_to_extendable();
self.as_extendable().push(c)
}
pub fn pop(&mut self) -> Option<u8> {
self.transform_to_extendable();
self.as_extendable().pop()
}
pub fn as_slice(&self) -> &[u8] {
match self {
Str::Extendable(s, _) => s.as_ref(),
Str::Owned(s, _) => s.as_ref(),
Str::Ref(s) => s,
}
}
pub fn len(&self) -> usize {
self.as_slice().len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn resize(&mut self, new_len: usize, value: u8) {
self.transform_to_extendable();
self.as_extendable().resize(new_len, value);
}
pub fn iter(&self) -> Copied<Iter<u8>> {
match self {
Str::Extendable(v, _) => v.iter(),
Str::Owned(v, _) => v.iter(),
Str::Ref(v) => v.iter(),
}
.copied()
}
pub fn iter_mut(&mut self) -> IterMut<u8> {
self.transform_to_owned();
self.as_mut_slice().iter_mut()
}
pub fn sort(&mut self) {
self.transform_to_owned();
self.as_mut_slice().sort_unstable();
}
pub fn into_owned(mut self) -> Str<'static> {
self.transform_to_owned();
match self {
Str::Extendable(v, _) => Str::Extendable(v, PhantomData),
Str::Owned(v, _) => Str::Owned(v, PhantomData),
_ => unreachable!(),
}
}
fn transform_to_extendable(&mut self) {
match self {
Str::Extendable(_, _) => {}
Str::Owned(_, _) => {
let mut fake = Str::new();
std::mem::swap(self, &mut fake);
if let Str::Owned(s, _) = fake {
*self = Str::Extendable(s.into_vec(), PhantomData)
} else {
unreachable!();
}
}
Str::Ref(s) => *self = Str::Extendable(s.to_vec(), PhantomData),
}
}
fn as_extendable(&mut self) -> &mut Vec<u8> {
match self {
Str::Extendable(s, _) => s,
_ => panic!("unreachable"),
}
}
fn transform_to_owned(&mut self) {
if let Str::Ref(s) = self {
*self = Str::Owned(s.to_vec().into_boxed_slice(), PhantomData)
}
}
pub fn as_mut_slice(&mut self) -> &mut [u8] {
self.transform_to_owned();
match self {
Str::Extendable(s, _) => s.as_mut_slice(),
Str::Owned(s, _) => s.as_mut(),
_ => panic!("unreachable"),
}
}
pub fn into_string(self) -> String {
match self {
Str::Extendable(v, _) => unsafe { String::from_utf8_unchecked(v) },
Str::Owned(v, _) => unsafe { String::from_utf8_unchecked(v.into_vec()) },
Str::Ref(v) => String::from_utf8_lossy(v).into_owned(),
}
}
pub fn reverse(&mut self) {
self.as_mut_slice().reverse();
}
pub fn trim(&self) -> Str<'_> {
let mut start = 0;
let mut end = self.len();
while start < end && (self[start] as char).is_whitespace() {
start += 1;
}
while start < end && (self[end - 1] as char).is_whitespace() {
end -= 1;
}
self[start..end].into()
}
pub fn split<'a, 'b>(&'a self, sep: impl Into<Str<'b>>) -> Vec<Str<'a>>
where
's: 'a,
{
let sep = sep.into();
let mut res = Vec::new();
let mut start = 0;
for i in 0..self.len() {
if self[i..].starts_with(sep.as_slice()) {
res.push(self[start..i].into());
start = i + sep.len();
}
}
res.push(self[start..].into());
res
}
pub fn parse<F: FromStr>(self) -> F
where
F::Err: Debug,
{
self.into_string().parse().unwrap()
}
pub fn parse_vec<T: Readable>(&self) -> Vec<T> {
let mut bytes = self.as_slice();
let mut input = Input::new(&mut bytes);
let mut res = Vec::new();
while !input.is_exhausted() {
res.push(input.read());
}
res
}
pub fn qty(&self, from: u8, to: u8) -> Vec<usize> {
let mut res = vec![0; (to - from + 1) as usize];
for &c in self.as_slice() {
res[(c - from) as usize] += 1;
}
res
}
pub fn qty_lower(&self) -> Vec<usize> {
self.qty(b'a', b'z')
}
}
impl<'s> IntoIterator for Str<'s> {
type Item = u8;
type IntoIter = IntoIter<u8>;
#[allow(clippy::unnecessary_to_owned)]
fn into_iter(self) -> Self::IntoIter {
match self {
Str::Extendable(v, _) => v.into_iter(),
Str::Owned(v, _) => v.into_vec().into_iter(),
Str::Ref(v) => v.to_vec().into_iter(),
}
}
}
impl From<String> for Str<'static> {
fn from(s: String) -> Self {
Str::Extendable(s.into(), PhantomData)
}
}
impl<'s> From<&'s str> for Str<'s> {
fn from(s: &'s str) -> Self {
Str::Ref(s.as_bytes())
}
}
impl From<Vec<u8>> for Str<'static> {
fn from(s: Vec<u8>) -> Self {
Str::Extendable(s, PhantomData)
}
}
impl<'s> From<&'s [u8]> for Str<'s> {
fn from(s: &'s [u8]) -> Self {
Str::Ref(s)
}
}
impl<'s, const N: usize> From<&'s [u8; N]> for Str<'s> {
fn from(s: &'s [u8; N]) -> Self {
Str::Ref(s)
}
}
impl<'s> From<&'s String> for Str<'s> {
fn from(s: &'s String) -> Self {
Str::Ref(s.as_bytes())
}
}
impl<'s> From<&'s Vec<u8>> for Str<'s> {
fn from(s: &'s Vec<u8>) -> Self {
Str::Ref(s.as_slice())
}
}
impl From<u8> for Str<'static> {
fn from(c: u8) -> Self {
Str::Owned(Box::new([c]), PhantomData)
}
}
impl From<char> for Str<'static> {
fn from(c: char) -> Self {
Str::from(c as u8)
}
}
impl<'s, 't: 's> From<&'s Str<'t>> for Str<'s> {
fn from(value: &'s Str<'t>) -> Self {
Str::Ref(value.as_slice())
}
}
impl<R: SliceIndex<[u8]>> Index<R> for Str<'_> {
type Output = R::Output;
fn index(&self, index: R) -> &Self::Output {
self.as_slice().index(index)
}
}
impl<R: SliceIndex<[u8]>> IndexMut<R> for Str<'_> {
fn index_mut(&mut self, index: R) -> &mut Self::Output {
self.transform_to_owned();
self.as_mut_slice().index_mut(index)
}
}
impl Clone for Str<'_> {
fn clone(&self) -> Self {
match self {
Str::Extendable(s, _) => s.clone().into(),
Str::Owned(s, _) => s.to_vec().into(),
Str::Ref(s) => Str::Ref(s),
}
}
}
impl<'r, 's, S: Into<Str<'r>>> AddAssign<S> for Str<'s> {
fn add_assign(&mut self, rhs: S) {
self.transform_to_extendable();
self.as_extendable()
.extend_from_slice(rhs.into().as_slice());
}
}
impl<'r, 's, S: Into<Str<'r>>> Add<S> for Str<'s> {
type Output = Str<'s>;
fn add(mut self, rhs: S) -> Self::Output {
self += rhs;
self
}
}
impl Readable for Str<'static> {
fn read(input: &mut Input) -> Self {
input.next_token().unwrap().into()
}
}
impl Writable for Str<'_> {
fn write(&self, output: &mut Output) {
for c in self.as_slice() {
output.put(*c);
}
output.maybe_flush();
}
}
impl Display for Str<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
<String as Display>::fmt(&String::from_utf8(self.as_slice().to_vec()).unwrap(), f)
}
}
impl Hash for Str<'_> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.as_slice().hash(state);
}
}
impl<'r> PartialEq<Str<'r>> for Str<'_> {
fn eq(&self, other: &Str<'r>) -> bool {
self.as_slice().eq(other.as_slice())
}
}
impl Eq for Str<'_> {}
impl<'r> PartialOrd<Str<'r>> for Str<'_> {
fn partial_cmp(&self, other: &Str<'r>) -> Option<Ordering> {
self.as_slice().partial_cmp(other.as_slice())
}
}
impl Ord for Str<'_> {
fn cmp(&self, other: &Self) -> Ordering {
self.as_slice().cmp(other.as_slice())
}
}
impl FromIterator<u8> for Str<'static> {
fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self {
Self::Extendable(iter.into_iter().collect_vec(), Default::default())
}
}
impl<'r> FromIterator<&'r u8> for Str<'static> {
fn from_iter<T: IntoIterator<Item = &'r u8>>(iter: T) -> Self {
Self::Extendable(iter.into_iter().cloned().collect_vec(), Default::default())
}
}
impl Deref for Str<'_> {
type Target = [u8];
fn deref(&self) -> &Self::Target {
self.as_slice()
}
}
impl DerefMut for Str<'_> {
fn deref_mut(&mut self) -> &mut Self::Target {
self.as_mut_slice()
}
}
pub trait StrReader {
fn read_str(&mut self) -> Str<'static>;
fn read_str_vec(&mut self, n: usize) -> Vec<Str<'static>>;
fn read_line(&mut self) -> Str<'static>;
fn read_line_vec(&mut self, n: usize) -> Vec<Str<'static>>;
fn read_lines(&mut self) -> Vec<Str<'static>>;
}
impl StrReader for Input<'_> {
fn read_str(&mut self) -> Str<'static> {
self.read()
}
fn read_str_vec(&mut self, n: usize) -> Vec<Str<'static>> {
self.read_vec(n)
}
fn read_line(&mut self) -> Str<'static> {
let mut res = Str::new();
while let Some(c) = self.get() {
if c == b'\n' {
break;
}
res.push(c);
}
res
}
fn read_line_vec(&mut self, n: usize) -> Vec<Str<'static>> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.read_line());
}
res
}
fn read_lines(&mut self) -> Vec<Str<'static>> {
let mut res = Vec::new();
while !self.is_exhausted() {
res.push(self.read_line());
}
if let Some(s) = res.last() {
if s.is_empty() {
res.pop();
}
}
res
}
}
impl Index<Back> for Str<'_> {
type Output = u8;
fn index(&self, index: Back) -> &Self::Output {
&self[self.len() - index.0 - 1]
}
}
impl IndexMut<Back> for Str<'_> {
fn index_mut(&mut self, index: Back) -> &mut Self::Output {
let len = self.len();
&mut self[len - index.0 - 1]
}
}
impl AsRef<[u8]> for Str<'_> {
fn as_ref(&self) -> &[u8] {
self.as_slice()
}
}
}
}
}
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,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2224kb
input:
3 3 6 ULDDRR 010 111 010
output:
-1 4 2 1 0 0 0 0 0
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 2288kb
input:
3 3 6 ULDDRR 010 111 011
output:
7 4 2 1 1 0 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 2244kb
input:
1 5 1 R 11111
output:
4 3 2 1 0
result:
ok 5 number(s): "4 3 2 1 0"
Test #4:
score: 0
Accepted
time: 1692ms
memory: 28828kb
input:
1 200000 200 RDRLDRULURDLDRULLRULLRRULRULRDLLDLRUDDLRURLURLULDRUUURDLUDUDLLLLLURRDURLUDDRRLRRURUUDDLLDDUUUDUULRLRUDULRRUURUDDDDLULULLLLLLLLLLLUDURLURLRLLRRRURUURLUDULDUULRRLULLRUDRDRUUDDRUDRDLLDLURDDDURLUULDRRDLDD 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
3999923 3999865 3999864 3999740 3999729 3999728 3999727 3999726 3999725 3999724 3999723 3999665 3999664 3999540 3999529 3999528 3999527 3999526 3999525 3999524 3999523 3999465 3999464 3999340 3999329 3999328 3999327 3999326 3999325 3999324 3999323 3999265 3999264 3999140 3999129 3999128 3999127 3999...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 973ms
memory: 20832kb
input:
2 100000 200 UULDRDLURDLDDRDRDUULDLUUULLRURLUUDDDRURURLLRRUDLDDDUDDRRUUURDDULURURLRULLUDLULURUUDURLDRRRDULRDLRRLDUUUDDUUDUDRDRUDLDRRUDRDLDRDLDRRDLRRDRDLRRLUDUDRULLRRLDDLUDDULDRLLLDLURRDDULDDUDULLRRRUURLRRRLURDLRLU 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 384513 384490 384313 384290 384113 384090 383913 383890 383713 383690 383513 383490 383313 383290 383113 383090 382913 382890 382713 382690 382513 382490 382313 382290 382113 382090 381913 381890 381713 381690 381513 381490 381313 381290 381113 381090 380...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 590ms
memory: 20940kb
input:
5 40000 200 URDDRRUDURLDLUUDUUDDLRRRURULURDRRURRURULUULRRLDLLDUURRDRUULRULULUDRURRRURDDLLDDRLLLUDUDLLDDULUUUULDLDUDLULLDRURRDRDULURLLLUDLRRRDRLUDDUURULURRRDLDRUDLURUUULDLURDDDRRLLLDLRRDLDLDRRURRRRDLRRLLULRRLDUULD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1000036 999836 999636 999436 999236 999036 998836 998636 998436 998236 998036 997836 997636 997436 997236 997036 996836 996636 996436 996236 996036 995836 995636 995436 995236 995036 994836 994636 994436 994236 994036 993836 993636 993436 993236 993036 992836 992636 992436 992236 992036 991836 99163...
result:
ok 200000 numbers
Test #7:
score: 0
Accepted
time: 502ms
memory: 20404kb
input:
10 20000 200 UULRURURUDRUULRRRDDDULUURRDUURDLDLLURRDUDDRDULRDURLDDLRRRRRRURLLUUURURDDUDDLLRDRLDDDDRULDRLLDUDLLLUDRURLDDLRRULDRRLLRRRDLRUDDDRRLDLRUDRUUDDDLUDULLDLUDUDUUUDLLRUURRLRLLDLLLLRLLRRDRRLLUDDURDRRDDULLDDULR 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
571658 571458 571258 571058 570858 570658 570458 570258 570058 569858 569658 569458 569258 569058 568858 568658 568458 568258 568058 567858 567658 567458 567258 567058 566858 566658 566458 566258 566058 565858 565658 565458 565258 565058 564858 564658 564458 564258 564058 563858 563658 563458 563258...
result:
ok 200000 numbers
Test #8:
score: 0
Accepted
time: 926ms
memory: 20120kb
input:
20 10000 200 UUDUUDRDLLLURLULDRULUDLRURRUUDLDLUURUDURDRUULULULUURRDDDLUDLLRDDLDULLDURLRRUULLRDULUUDDLRDLDRDLDULULRLLLLUDUUUDDLDLLRLUUDLURLULLURDDDLLLUDDDLRDULLUUDRLDLRDLRLURRUUDLRULURRLLLURRUDLDUDRLUDDRDUUULLDDUDL 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
83411 83305 83211 83105 83011 82905 82811 82705 82611 82505 82411 82305 82211 82105 82011 81905 81811 81705 81611 81505 81411 81305 81211 81105 81011 80905 80811 80705 80611 80505 80411 80305 80211 80105 80011 79905 79811 79705 79611 79505 79411 79305 79211 79105 79011 78905 78811 78705 78611 78505 ...
result:
ok 200000 numbers
Test #9:
score: 0
Accepted
time: 1424ms
memory: 21804kb
input:
50 4000 200 LUDLUULUUUDUDDUDRULLDDRDRDLDUDRUUDUUUDULDUURDUUDLRUDDDURURRRUDDRUDDRURURURUDLLLDRURLLRRURRLULDDLLURULRDURDDLURURDDURDDRURRDDDULUURLUDRRUULRLURUDULLRURUUDLRDDLULUDRULDRRLRRLURDLUDDRDRLRRDDULRULDLURRRUL 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
53472 53272 53072 52872 52672 52472 52272 52072 51872 51672 51472 51272 51072 50872 50672 50472 50272 50072 49872 49672 49472 49272 49072 48872 48672 48472 48272 48072 47872 47672 47472 47272 47072 46872 46672 46472 46272 46072 45872 45672 45472 45272 45072 44872 44672 44472 44272 44072 43872 43672 ...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 1028ms
memory: 19728kb
input:
100 2000 200 UDULUDLDUUDDUDLURDRDLDDLLDRLLDUURUDLLUURLRLLRDLUUUURLLUDRRUDUDDLRLLLDDUUDDULRUUULLRRUUUUUDRLLUUUURDUDLUUDLUDDRRULRLRLUDLRLRRRLRULULLRLLURRUUUDRLRRRRLUURULURUUUUDURRDDDRLLLLULDUDRLDURUUDDRRRULULRLRDULD 10111111111111111111111111111111111111111111111111111111111111111110111111111100111111...
output:
-1 -1 47281 47081 46881 46681 46481 46281 46081 45881 45681 45481 45281 45081 44881 44681 44481 44281 44081 43881 43681 43481 43281 43081 42881 42681 42481 42281 42081 41881 41681 41481 41281 41081 40881 40681 40481 40281 40081 39881 39681 39481 39281 39081 38881 38681 38481 38281 38081 37881 37681 ...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 1113ms
memory: 19900kb
input:
200 1000 200 RLRDLDRDUDLRDULDLLURDULDLLDUDLULLLUUUDLRRRUDLUUUDDRLULRRLDLDLLDRLLLURDLDRRRLULUDDLUDUULULUULDRRURDDLUUULURULRUUDRRLRDULDUDRLDLRUDRLULLLLRLLDRDLDLRDUUUUUULUDLDRUDDUUDRLDRUDUUDLULLDDURLRULLRULDRLLRDLURR 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 10432 10232 10062 10032 9994 9887 9862 9832 9794 9687 9662 9632 9594 9487 9462 9432 9394 9287 9262 9232 9194 9087 9062 9032 8994 8887 8862 8832 8794 8687 8662 8632 8594 8487 8462 8432 8394 8287 8262 8232 8194 8135 8087 8062 8032 7994 7935 7887 7862 7832 7794 7736 7735 7687 7662 7632 7594 7553 753...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 1144ms
memory: 20016kb
input:
400 500 200 RULLRRRDLUDDRLDDRDLRLDLDLUUDRUDDULRDDLDULULLRUDULRLRLRUDURDRDDDLDRUDRLRDRLRDLULLLLRURRLRRULULDLDRDDULDDUULURLRLLDUUUUDDUDURLULRLDRLDDRULUDDLLRRDDULLDLURDLDRLLULRLRUULRLLLRULRUDLRRRLURUULLLDDDUDRDLRURD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
9541 9370 9369 9341 9244 9243 9170 9169 9141 9103 9044 9043 9039 9039 9022 8987 8970 8969 8960 8941 8903 8876 8865 8844 8843 8839 8839 8824 8822 8787 8770 8769 8760 8750 8741 8703 8676 8676 8665 8644 8643 8639 8639 8624 8622 8588 8587 8570 8569 8560 8550 8541 8503 8503 8476 8476 8465 8444 8443 8439 ...
result:
ok 200000 numbers
Test #13:
score: 0
Accepted
time: 1150ms
memory: 20240kb
input:
447 447 200 LULRUURRDLDUDDRDRLDDUDLRLURUDLLDDLRLRDLURURRDRDDDRRDDLLDRDDDUDULLRLURLLURULLLLRUUULDRDRRDDULULRLURDDUDURDULUURRLDURURDDUDDDDURRLRLLDLULDRURDUUURLRULURUULURURUDDRDDDDLLRRLLLDRLRDDRRLDDRULLLLRURDRUULRUU 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 22650 22450 22250 22050 21850 21650 21450 21250 21050 20850 20650 20450 20250 ...
result:
ok 199809 numbers
Test #14:
score: 0
Accepted
time: 1188ms
memory: 20440kb
input:
500 400 200 DUUDRULRRRULLDUDDULULLRRDUDRULDRUURUDLDLDDDDRDLDUDRLDLDDURUDDLDLLLRLURDRULDLRLDRRUDRRULURDLDDDLULRLLRRDLUDLLULUULLRLLUURLDDULLRRDDRULUDRRLRRDURLLLDRDRRRLUDUUDUDDLRUDUDLRLDRLURULUULDUDLLDURDLLDDLRLULLU 111111111111111111111111111111111111111111111111011111111111111111111111111111111111111...
output:
11256 11056 10856 10656 10456 10256 10056 9856 9656 9456 9256 9065 9056 8865 8856 8665 8656 8469 8465 8456 8269 8265 8256 8069 8065 8056 7918 7879 7869 7865 7856 7718 7679 7669 7665 7656 7518 7511 7479 7469 7465 7456 7434 7318 7311 7311 7279 7269 7265 7256 7234 7118 7111 7111 7094 7079 7069 7065 705...
result:
ok 200000 numbers
Test #15:
score: 0
Accepted
time: 1225ms
memory: 20192kb
input:
1000 200 200 LRUURLUDLDRURRLRLDRDLURDRUDUULDRLULLLRURRURDLULDULDDUDUULRLRDRLRLUDURULRDLDDLUURULDURDLLRUUDURDLURDDDUDRURRDRUUUUDLRUULRDDRLULDURLRDURDLDRRULRURLRUDLRRUUDRRDDLLUULDDDRDLRURLDLRDDULDDDUUDDRURURDDLRRRDR 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 20999 20799 20599 20399 20199 19999 19799 19599 19399 19199 18999 18799 18599 18399 18199 17999 17799 17799 17599 ...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 1161ms
memory: 20064kb
input:
2000 100 200 LRLUUDDLLUURLDRUUDUDRRULRDRDURURLRLLLRDLULLDRRRULDUDRDDRRRDUUDDDRLLULDRULRDDLDUULRDUDLRUUUDRDLRLDDUDLLDLLUDDLDRLRLURURLRRRLUULLLDLRLULDRRRLURDRDLRUDDLLLLRUDRLRLLRUDRDLUDLDRDDDLDUDLRDUURDRDUDDDUUDURUUU 11111111111111111111111111111111111111111111111111111111111111111111101111111111111111...
output:
-1 -1 -1 -1 -1 41180 40980 40780 40580 40380 40180 39980 39780 39580 39380 39180 38980 38780 38580 38380 38180 37980 37780 37580 37380 37180 36980 36780 36580 36380 36180 35980 35780 35580 35380 35180 34980 34780 34580 34380 34180 33980 33780 33580 33380 33180 32980 32780 32580 32380 32180 31980 317...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 1403ms
memory: 21992kb
input:
4000 50 200 DRUDDUDULRURRULUUDLLUUURUURLLDUDRRUULULDLRRLUDURLRUDDLRRDLUDURUULRDRURUDUDRDLDUDLDURULURRLRRRDRDRRRDRDUDLUDRDUDLRLDDULLLLLUDRDLLUDRRRLUURDUULLRRLLRLDDLDRDDDUDLRRRURDRLLUDUUURLLDDLLRRLLDRUDRUULUULRURDR 11111111111111111111111111111111111111111111111111 111111111111111111111111111111111111...
output:
-1 112736 112536 112336 112136 111936 111736 111536 111336 111136 110936 110736 110536 110336 110136 109936 109736 109536 109336 109136 108936 108736 108536 108336 108136 107936 107736 107536 107336 107136 106936 106736 106536 106336 106136 105936 105736 105536 105336 105136 104936 104736 104536 104...
result:
ok 200000 numbers
Test #18:
score: 0
Accepted
time: 991ms
memory: 20272kb
input:
10000 20 200 UDLLURURULUUUDDLDRDRLDLRUULDLUUULUULLRRDUUDDLRDRRLUDUDLRRLUURLURRLULRRURLRRLLDLULUDRRDUUUDURRURLDDRRDRRDLDURDRLLURDDDDDURULRULULLUURLUDUUUUDDLURULRUDLUDDRLLUDRLDRRULUDRDUDRUDDDLLRRURULULDLLUDLLRUDRDRL 11111111111111111111 11111111111111111111 11111111111111111111 11111111111111111111 11...
output:
182271 182071 181871 181671 181471 181271 181071 180871 180671 180471 180271 180071 179871 179671 179471 179271 179071 178871 178671 178471 178271 178071 177871 177671 177471 177271 177071 176871 176671 176471 176271 176071 175871 175671 175471 175271 175071 174871 174671 174471 174271 174071 173871...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 555ms
memory: 18572kb
input:
20000 10 200 RULRLRLLLRUUDLLDDUDUURUUUUDUUDDRDDUULRRLDRDDRRLUURRLUDUDURUDRUDLDLDDURLRDRRRRUDRDLRRRULLLDLRURRDUUURURUDUUUDLLLRDLDDDLRULUDDURRUUDDDLURLDURRRRDLLLDRUDDDULRRLRDURRDURDDUDDUDLDRLLLULLULRULULLRLUUDRLDLDL 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #20:
score: 0
Accepted
time: 586ms
memory: 19796kb
input:
40000 5 200 LDULRUULURUDRDLRUDUDURUUUDDRLUDDRUDUUUUDURUDUURDRLURLDURDUDRUULURUURRRRURRRLRLUUUULLLLDLDLRUUDDLDRLDURRRRUULDDLRRLRUUUDDRDRDRLLLLRDURLLLLDRRUULLDRLRULRURUDDURLDDRRRULUDULDULRDLDLRLRUUUDRLRRUUDLRULURRD 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 111...
output:
444424 444224 444024 443824 443624 443424 443224 443024 442824 442624 442424 442224 442024 441824 441624 441424 441224 441024 440824 440624 440424 440224 440024 439824 439624 439424 439224 439024 438824 438624 438424 438224 438024 437824 437624 437424 437224 437024 436824 436624 436424 436224 436024...
result:
ok 200000 numbers
Test #21:
score: 0
Accepted
time: 968ms
memory: 21528kb
input:
100000 2 200 RRULURDRDDUULLLURURULUDRRDLULURRULUURDURDRRLDDRLRDLRLURRDDDRRDRLDDLUDRLUDDLLUDRLDRURLLDDLRURRRLLLLUULRULUDRRLLLLRLLUUULURDDDRRDRDULLLUULLRDDRUDUURRRLURURDLULURLURLDLRULUDDDRULRUDRLUDLDLLLUURDDLRLLULUU 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11...
output:
-1 -1 -1 -1 -1 -1 -1 829117 828917 828717 828517 828317 828117 827917 827717 827517 827317 827117 826917 826717 826517 826317 826117 825917 825717 825517 825317 825117 824917 824717 824517 824317 824117 823917 823717 823517 823317 823117 822917 822717 822517 822317 822117 821917 821717 821517 821317...
result:
ok 200000 numbers
Test #22:
score: 0
Accepted
time: 1719ms
memory: 29564kb
input:
200000 1 200 RUDRUUULRUDURLULRLLLRLDLLUURRLURRDDRLRLLDDUULDRURDLRRRLLLRRURURLDRUURLLRRRRLULLURLDULDLUURLLRUDLRRRRURLDRLLDDUUURDRUUULRLDRDLULRRUDRRDDDRLRDLUDLDUUULDDRUUDLULRDULLURUULLRULLUDDRDDLLRRUUUDULDLDRDLLDDDU 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
4444289 4444280 4444277 4444231 4444174 4444171 4444118 4444117 4444094 4444089 4444080 4444077 4444031 4443974 4443971 4443918 4443917 4443894 4443889 4443880 4443877 4443831 4443774 4443771 4443718 4443717 4443694 4443689 4443680 4443677 4443631 4443574 4443571 4443518 4443517 4443494 4443489 4443...
result:
ok 200000 numbers
Test #23:
score: 0
Accepted
time: 1631ms
memory: 22656kb
input:
447 447 200 DRUDULRLDRLUUUDRRDULUDRUURRRLDRDUDULDRLRLUDLDRURDRDUULRRUDRRLDULLRRLDDRRDRLRDRLRLDDRRULDLRDRUDRUDDRRLRRULDDDLRLRURLLULLDLDDRDDULRULURDULDULULRURDLLLRUDUUUURUDRDRLRLDRURRLLLURDUDDDDULLRDRDUDLDULLRULLLD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
12700 12500 12485 12478 12474 12316 12300 12285 12278 12277 12274 12144 12116 12100 12085 12078 12077 12074 11944 11916 11900 11885 11878 11877 11874 11744 11716 11700 11685 11678 11677 11674 11544 11516 11500 11485 11478 11477 11474 11344 11316 11300 11285 11278 11277 11274 11144 11116 11100 11085 ...
result:
ok 199809 numbers
Test #24:
score: 0
Accepted
time: 665ms
memory: 18368kb
input:
447 447 200 RRUULDLLULUUDLDUUDDRLDUDLLDLUURDLDURLUDUDLRRDDDDUUULRDDRDURDDDLDRDDLRDDLULUDLURDDRUUDUUDUDLRRDRUDDUUDLRRUDLRDDLUUUDDURDLDDLULUURUURDDLLUDRDRDLLLRDRLUDLLRDUDRRRDURUDLLLUUUDULLRRUDRLLLDDLURUUDRLDDRUUURL 110111111111111111111111111111111111011111111111111111111111111111101111111101111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12867 12667 12667 12467 12467 12267 12267 12067 12067 11867 118...
result:
ok 199809 numbers
Test #25:
score: 0
Accepted
time: 533ms
memory: 18072kb
input:
447 447 200 LULULUDRURRURLDRLUUDDLDUDRLLUDRLLLLDDUULLLLRLUDLRRLDRRRLURRULULURRRUULUUDRLUDDLRRDDRLLURLDDULLDURDULRRURULLRUURLUUUULULLDLRLDLULULDDRDUDRULUUDUUDRRRDRURUUDLDDRRLDLRLLULLRLURDDULRLUDLRLUDUDUDLLRRUULDDU 111101111111111101111111111110011111101101111111111111111111111111111111111001011101111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9719 9519 9433 9319 9233 9119 9033 8919 8833 8719 8633 8519 8433 8319 8233 8130 8119 8033 7930 7919 7833 773...
result:
ok 199809 numbers
Test #26:
score: 0
Accepted
time: 372ms
memory: 16828kb
input:
447 447 200 UDUDDURLLULURDRLLDLLRDDRDRUDRRRURLRDRDDURURDUUDRUUDURDRLULLRLDDLRURUDDRDULDUDDRLLDDRRULURRUUDDURRURDRRLUDLRLLDLUUDDLUDUULLLLUULDURRDDRDDLULLULDRLRLLUURLDUDRUDDLUUULUDUUUDUUDLUDDRLDDDRRDUURUUDDDRDLRLRL 001100011110110011011100101110111101101001000011011010011001100100000111110101010100100...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 199809 numbers
Test #27:
score: 0
Accepted
time: 151ms
memory: 15824kb
input:
447 447 200 DRLLUUDDULDRRDDDLLRRLUDLUURULDLRUDULDLLLRLDLLUDUDDULRUULRDDLDLUDRDRUDRRLLDDUDLDLULLUULRDRDRUUURDRRRDRRUULLDUUDDDUDRUDLRLRRLRUDDURULUUULULDDRRRLRURDLRDLDRUUDRUUDRRLDLUULLRLURURRURLLDDLRRLRURLRURULUULLR 000010000000000000101000000000100000000000000000000000000000001000000000000000000000000...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 199809 numbers
Test #28:
score: 0
Accepted
time: 665ms
memory: 18720kb
input:
100 2000 200 DURRLLDURUUDULRRUDRRUDLURRDUURLUURLUDLRURLRLRRRURDDRULRRULLUUDUDRDLUDDRRDRRDULUDUDULDRDLRUUULLRLULURRRRDDRUULDLLDUDDRLDURLULURUDRLRDLULRDLLLDRLDULLRRDLDURDUURLDLLRLLDDURUDRDDLUURDURRULRRRDDLLRRDURRDDU 11110111111111111011111111111111111011111111111111110111111111111111111111111011111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 32875 32675 32475 32275 32075 31875 31675 31475 31275 31075 30875 30675 30475 30275 30075 29875 29675 29475 29275 29075 28875 28675 28475 28275 28075 27875 27675 27475 27275 27075 26875 26675 26475 26275 26075 25875 25675 25475 25275 25075 24875 24675 24475 242...
result:
ok 200000 numbers
Test #29:
score: 0
Accepted
time: 686ms
memory: 18384kb
input:
200 1000 200 UDDLRLLURDDRDLRURLUURDRRRUULUULLRDDLRRDUUDDULDDUULULLLRDRUUDRRULRDLLUUDURDLDUURLRDDUDRURDRLRUDRLURUULDRLURUURLRULUUULLLRUDDDLRULLLRRDULUDDURURUURDUUULDRURDDDULULRRULRLLULULLURDDLDRRULLLULDLUDLLRDDUDRL 11111111111111111111111111011111111111111111110111111111111111110111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4972 4792 4772 4718 4592 4572 4518 4399 4392 4372 4359 4318 4207 4199...
result:
ok 200000 numbers
Test #30:
score: 0
Accepted
time: 642ms
memory: 18380kb
input:
400 500 200 URDRUUDRDUUDRRRUUDLDDLRRRLRULLRDDDULRURUURLLRDLULURRURRRLLRRLDUDLDRRRLLUUUDULLDRRDDRULULDUUDDRLRUURRRLDDRRUDRDDDDDLLURDLDUDDLRURLDRUUDUDRURURLDURRULDRLDDRLRLDLLUURUULRRRULLUDDLDRRDLDRRDRRURLURLDULDDLU 111111101111111111111111111111110111111101111011111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8513 8434 8353 8313 8234 8153 8113 8034 7953 7953 7913 7900 7834 7753 7753 7713 7700 7634 7553 7553 7553 7513 7500 7434 7398 7358 7353 7353 7353 7352 7313 7300 7234 7198 7158 7153 7153 7153...
result:
ok 200000 numbers
Test #31:
score: 0
Accepted
time: 719ms
memory: 18416kb
input:
500 400 200 LRLLDDDLLRRLLRDURRLLDLUDLLRDRULRURULUDURRUDDRLRDRLURRDURLLLDLRUDRDLUURUDDUUDUUDUURRLDRURLDULDRLLLDDUUUULRDLUDURLLRDRRLUDLLRLURUULUURDRULLDDDLRDLRUURDUUDRDLDRURDDURUDUDRUUUDURUUDURDUUDURLDDRUDDDRLRLRDR 111111111111101101111111011111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #32:
score: 0
Accepted
time: 709ms
memory: 18408kb
input:
1000 200 200 RLRDURLUDDLRRURLUDRLUUURULRLLULRRRRUDLRRDLUULDRDURLDLURLUDULLRDLRLDLRUDLLRRULLUUDDRRDUUULUDLRLDUDLUURDUUURRUULRLRLUUDLLLULUDLRLDUUUURDUDRRDLRDLRRLRULDDRULURDUULULLUDDLLUDRURURRUDRUDLDRLRLDLUULLRUUUUDD 11111111110111111101111111110111111111111111011111111111111110101111111110111111011111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11932 11732 11725 11596 11532 11525 11520 11396 11393 11332 11325 11320 11196 11193 11132 11125 11120 10996 10993 10932 10925 10920 10829 10796 10793 10732 10725 10720 10629 10596 10593 10532 10525 10520 10429 10396 10393 10332 10325 10320 10229 10196 10193 ...
result:
ok 200000 numbers
Test #33:
score: 0
Accepted
time: 697ms
memory: 18432kb
input:
2000 100 200 RLDDDLUDDURRDLURDUULDRDUURDULDDRLLRUDDULDDRURDUULLDDDUULDDRUUDRUUDLLLULRRDRULRUDURRRRDULRRLUUDRULRRUURURDUDULULDLLLUDDLLLURRDRRRDDDDRUULDLULUULURLLDDUUDRUDDRDDLLDUDRDDDLUUURRLLUUUDLLURURURRLUUUDUUDDUL 01111111111101111111110111111111111111011111111111111111111111111111111111111111101111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #34:
score: 0
Accepted
time: 536ms
memory: 17816kb
input:
100 2000 200 UDDRLDUDRDRLLLRDLRLDLDULLULUUULDUUULULLDDDLLULRDLURLUUULRDRRLURURLULLLDULRUULURUDRDLRUDUDURUUUDDRLUDDRUDUUUUDURUDUURDRLURLDURDUDRUULURUURRRRURRRLRLUUUULLLLDLDLRUUDDLDRLDURRRRUULDDLRRLRUUUDDRDRDRLLLLRD 11111111111111111111111111111011011111111011111110111111111111100111111110111111110111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #35:
score: 0
Accepted
time: 603ms
memory: 17860kb
input:
200 1000 200 ULRLUUDDRLUURDRRDULLDDULLLDLRULRRRRULRULLDRDRUUDLDLLLRUULRDUDLRDRLRUDDUDULUULDLUURLRRUUURRDURLDLRUURUDULRDUDLDULLURRURURULDLDDRDRRUURRULRLDURRLLDRUDDUURLLLRRLDLRDDRLRUULLDLRLDDRUUDRUULRDRDLDULULLULLDU 11111111111111111111111111111111111111111111111111111111101111101111111111111110111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #36:
score: 0
Accepted
time: 565ms
memory: 17936kb
input:
400 500 200 RURRDRUULDRLDRRLLRURRLUDLRURLLRLDRLURURLDLDLUULDURDLDUULDDULRDUULRDLURDDUURRDRULDRLRLUURUURLUUURRURDDRDDRUUDLULRDDDULULLLUDLDDRRLRUDDULLUDUDLDRLUUURLLULRLRDURLUDLDRDLDDDRRLDURLLDLRDDDRRDUURRRRRRDDRLUD 111111100111111111111111111111111111111111101110111101111011111110101111111111111110101...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #37:
score: 0
Accepted
time: 553ms
memory: 18232kb
input:
500 400 200 DUULDRURLULRULDLULUURLLUDRUDRULUDULUUDUUURUDUDRLLDLLRRDDDDLRRLRURLULDURRLULULLULLDUDLUUUUDRRRDUDDDDLLUDLRRLUURUULRULDRLDLLRURDRURDDULDLRRLLLDLRUULUURRRLUURLDLLURRULLURDLRDDDLLURLRRUURDDULLRDDDRLRLUURD 011110111111111111101111101111111111111111110111111011111111111111111111111111111010011...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11623 114...
result:
ok 200000 numbers
Test #38:
score: 0
Accepted
time: 533ms
memory: 17940kb
input:
1000 200 200 RRDDDLLDLLDUDURDLRDURUDDRUULLDLURUDDULLDLLRDRURLLLUULLUURDUDURUURURUUUURRUDRDRRLRRULRDULUUURLRRRULULDDDURDRURDRURLRRRRRDDLDRUDDDDLDDDURRURLRLUUDURRDRRRRLLLDRLUULURRLDUULUDUDLDRLRRLULRRRURDLDRLRDDRRDLR 01111111111111111111101111111011111111111111111111111101111111111011111111111110111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #39:
score: 0
Accepted
time: 524ms
memory: 18432kb
input:
2000 100 200 LRRDLURLLDLUULULRRRURURRRULRLLDURRDLUDUURUDUUURDUURULLDUUDURLDRLULUDRDUUULDRDURRDUURURUUDRDDRLDRDRRLLRDRDDDUDLRRRRDRRLRDRURDUDRRLLLLDRLULRDRRRRLURLLLRRDURLRDRDUUUDRUDURURLUULULLLURLLLULUURRRUULUDRULDU 11111111111111101111110100111111011111111111110110111111111111111111110011111110111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 26086 25886 25686 25486 25286 25086 24886 24686 24486 24286 24086 23886 23686 23486 23286 23086 22886 22686 22486 22286 22086 21886 21686 21486 21286 21086 20886 20686 20486 20286 20086 19886 19686 19486 19286 19086 188...
result:
ok 200000 numbers
Test #40:
score: 0
Accepted
time: 597ms
memory: 21616kb
input:
66663 3 200 RUDLLUDRLUDRLDURRDULRDULLDDRUDLLDURLDURLUDRLUDRLDURRUDLRDULRUDLRDULLUDRRUDLRDULRDULRDULLUDRLDURLDURRUDLLUDRRUDLLDURRDULLUDRLUDRRDULRDULUDRUDLLUDRRDULLUDRRDULRDULLDURLUDRRUDLLDURRUULDURRDULLUDRLUDRRUDL 011 010 011 010 011 010 011 010 011 010 011 010 011 010 011 010 011 010 011 010 011 010...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 199989 numbers
Test #41:
score: 0
Accepted
time: 1133ms
memory: 37456kb
input:
66666 3 200 RURRLUUUULDLDRRRURURRLRULDLLRRRULURURULDUUDDDUURDRDLDRUUDLLUUULDDULULLLLLDLURUDURLDDDULRLDURRLURULRLDDURUDUDRDDLDDLLULDDLLLLDUDRDRLLRUDUULDLLRLLDDLRURRLURUDLUDUDDDUURDLRLDURRDRLRRDRDRLDDLLUDRRRRURRLUU 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101...
output:
-1 -1 -1 -1 13320869 13320681 13320669 13320481 13320469 13320281 13320269 13320081 13320069 13319881 13319869 13319681 13319669 13319481 13319469 13319281 13319269 13319081 13319069 13318881 13318869 13318681 13318669 13318481 13318469 13318281 13318269 13318081 13318069 13317881 13317869 13317681 ...
result:
ok 199998 numbers
Test #42:
score: 0
Accepted
time: 1524ms
memory: 15616kb
input:
200000 1 200 LRLLRRLLRLRRLRLLRRLRLLRRLLLLRLLRRRRRLRRLLRRLLLLLRLLRRRRRLRLLRLRLLRRRRLRLLRRLRLRLRRRRLLLLRRRRLRRLLRLRLLLLRLLRLLRLRRRLRLLLLRLLLLLLLLLLLRRRLRLRRRLRRRRLLRLLRLRLRRRLLRLRLLRLLRRLLLRLLLRRRRLRRRRLLLRRRRRRRRLR 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #43:
score: 0
Accepted
time: 1593ms
memory: 15508kb
input:
200000 1 200 DUDDUUUDDUUDUUUUDDDDUDDUDUDUUDDDUUDUUDUUUUUDDUDUDUUDDDUUUUDUUDDDDUDDUDDUDDDDUUUUUDUUUUUDUDUDDDDUUDUDDDDUDDUUUDUUDDDUDUUDUDUDDDUDDDDDUDUDUUDUUUDUUDDDUUDUDUDUUDDUUDDUUDDUUUUDUUUDDDDDDUUDUUDDUUDUUDUDDUDD 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 200000 numbers
Test #44:
score: 0
Accepted
time: 719ms
memory: 16952kb
input:
4 49999 200 RRRUUUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDULLDD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 199996 numbers
Test #45:
score: 0
Accepted
time: 714ms
memory: 28928kb
input:
4 49999 200 RRRUUUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDULLDD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 199996 numbers
Extra Test:
score: 0
Extra Test Passed