結果

問題 No.2210 equence Squence Seuence
ユーザー tomarinttomarint
提出日時 2023-02-10 22:47:05
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 17,211 bytes
コンパイル時間 14,024 ms
コンパイル使用メモリ 382,896 KB
実行使用メモリ 18,496 KB
最終ジャッジ日時 2024-07-07 16:50:49
合計ジャッジ時間 15,563 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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

#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_snake_case)]
// use proconio::input;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::io::{Read, Write};
use std::mem::swap;
//----------------------------------------------------------------------------
fn read<T: std::str::FromStr>() -> T {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
//----------------------------------------------------------------------------
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
//----------------------------------------------------------------------------
macro_rules! chmin {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_min = min!($($cmps),+);
if $base > cmp_min {
$base = cmp_min;
true
} else {
false
}
}};
}
macro_rules! chmax {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_max = max!($($cmps),+);
if $base < cmp_max {
$base = cmp_max;
true
} else {
false
}
}};
}
macro_rules! min {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::min($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::min($a, min!($($rest),+))
}};
}
macro_rules! max {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::max($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::max($a, max!($($rest),+))
}};
}
//----------------------------------------------------------------------------
const MOD: i64 = 998_244_353;
// const MOD: i64 = 1_000_000_007;
#[derive(Copy, Clone, PartialEq, Eq)]
pub struct Mint {
val: i64,
}
impl Mint {
pub fn new(n: i64) -> Self {
let mut new_val = n % MOD + MOD;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
pub fn pow(&self, n: i64) -> Self {
if n == 0 {
Self { val: 1 }
} else {
let mut ret = self.pow(n >> 1);
ret *= ret;
if (n & 1) != 0 {
ret *= *self;
}
ret
}
}
pub fn inv(&self) -> Self {
self.pow(MOD - 2)
}
}
impl std::fmt::Display for Mint {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl std::fmt::Debug for Mint {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl std::ops::Add for Mint {
type Output = Self;
fn add(self, other: Self) -> Self::Output {
let mut new_val = self.val + other.val;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
}
impl std::ops::Sub for Mint {
type Output = Self;
fn sub(self, other: Self) -> Self::Output {
let mut new_val = self.val + MOD - other.val;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
}
impl std::ops::Mul for Mint {
type Output = Self;
fn mul(self, other: Self) -> Self::Output {
Self {
val: (self.val * other.val) % MOD,
}
}
}
impl std::ops::Div for Mint {
type Output = Self;
fn div(self, other: Self) -> Self::Output {
if other.val == 0 {
panic!("0 division occured.");
}
self * other.inv()
}
}
impl std::ops::AddAssign for Mint {
fn add_assign(&mut self, other: Self) {
*self = *self + other;
}
}
impl std::ops::SubAssign for Mint {
fn sub_assign(&mut self, other: Self) {
*self = *self - other;
}
}
impl std::ops::MulAssign for Mint {
fn mul_assign(&mut self, other: Self) {
*self = *self * other;
}
}
impl std::ops::DivAssign for Mint {
fn div_assign(&mut self, other: Self) {
*self = *self / other;
}
}
//----------------------------------------------------------------------------
pub struct MintComb {
fact: Vec<Mint>,
ifact: Vec<Mint>,
}
impl MintComb {
pub fn new(n: i64) -> Self {
let mut obj = Self {
fact: vec![Mint::new(1); n as usize + 1],
ifact: vec![Mint::new(1); n as usize + 1],
};
assert!(n < MOD);
obj.fact[0] = Mint::new(1);
for i in 1..=n as usize {
obj.fact[i] = obj.fact[i - 1] * Mint::new(i as i64);
}
obj.ifact[n as usize] = obj.fact[n as usize].inv();
for i in (1..=n as usize).rev() {
obj.ifact[i - 1] = obj.ifact[i] * Mint::new(i as i64);
}
obj
}
pub fn permutation(&self, n: i64, k: i64) -> Mint {
assert!(n >= 0);
if k < 0 || n < k {
Mint::new(0)
} else {
self.fact[n as usize] * self.ifact[k as usize]
}
}
pub fn combination(&self, n: i64, k: i64) -> Mint {
assert!(n >= 0);
if k < 0 || n < k {
Mint::new(0)
} else {
self.fact[n as usize] * self.ifact[k as usize] * self.ifact[(n - k) as usize]
}
}
}
//----------------------------------------------------------------------------
//
#[derive(PartialEq, Debug, Copy, Clone, Eq, PartialOrd, Ord)]
struct Ratio {
numerator: i64, //
denominator: i64, //
}
//
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
impl std::fmt::Display for Ratio {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
if self.denominator == 1 {
write!(f, "{}", self.numerator)
} else {
write!(f, "{}/{}", self.numerator, self.denominator)
}
}
}
impl Ratio {
fn new(p: i64, q: i64) -> Ratio {
if q == 0 {
panic!("Ratio: divide by zero");
}
let g = gcd(p.abs(), q.abs());
let s = if q < 0 { -1 } else { 1 };
Ratio {
numerator: s * p / g,
denominator: s * q / g,
}
}
fn from_integer(n: i64) -> Ratio {
Ratio {
numerator: n,
denominator: 1,
}
}
fn as_int(&self) -> i64 {
self.numerator / self.denominator
}
fn as_float(&self) -> f64 {
self.numerator as f64 / self.denominator as f64
}
fn numer(&self) -> i64 {
self.numerator
}
fn denom(&self) -> i64 {
self.denominator
}
fn is_integer(&self) -> bool {
self.denominator == 1
}
}
impl std::ops::Add for Ratio {
type Output = Ratio;
fn add(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator + other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Sub for Ratio {
type Output = Ratio;
fn sub(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator - other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Mul for Ratio {
type Output = Ratio;
fn mul(self, other: Ratio) -> Ratio {
let p = self.numerator * other.numerator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Div for Ratio {
type Output = Ratio;
fn div(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator;
let q = self.denominator * other.numerator;
Ratio::new(p, q)
}
}
//----------------------------------------------------------------------------
pub trait BinarySearch<T> {
fn lower_bound(&self, x: &T) -> usize;
fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> BinarySearch<T> for [T] {
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
std::cmp::Ordering::Less => {
low = mid + 1;
}
std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
std::cmp::Ordering::Less | std::cmp::Ordering::Equal => {
low = mid + 1;
}
std::cmp::Ordering::Greater => {
high = mid;
}
}
}
low
}
}
//----------------------------------------------------------------------------
pub trait LexicalPermutation {
/// Return `true` if the slice was permuted, `false` if it is already
/// at the last ordered permutation.
fn next_permutation(&mut self) -> bool;
/// Return `true` if the slice was permuted, `false` if it is already
/// at the first ordered permutation.
fn prev_permutation(&mut self) -> bool;
}
impl<T> LexicalPermutation for [T]
where
T: Ord,
{
/// Original author in Rust: Thomas Backman <serenity@exscape.org>
fn next_permutation(&mut self) -> bool {
// These cases only have 1 permutation each, so we can't do anything.
if self.len() < 2 {
return false;
}
// Step 1: Identify the longest, rightmost weakly decreasing part of the vector
let mut i = self.len() - 1;
while i > 0 && self[i - 1] >= self[i] {
i -= 1;
}
// If that is the entire vector, this is the last-ordered permutation.
if i == 0 {
return false;
}
// Step 2: Find the rightmost element larger than the pivot (i-1)
let mut j = self.len() - 1;
while j >= i && self[j] <= self[i - 1] {
j -= 1;
}
// Step 3: Swap that element with the pivot
self.swap(j, i - 1);
// Step 4: Reverse the (previously) weakly decreasing part
self[i..].reverse();
true
}
fn prev_permutation(&mut self) -> bool {
// These cases only have 1 permutation each, so we can't do anything.
if self.len() < 2 {
return false;
}
// Step 1: Identify the longest, rightmost weakly increasing part of the vector
let mut i = self.len() - 1;
while i > 0 && self[i - 1] <= self[i] {
i -= 1;
}
// If that is the entire vector, this is the first-ordered permutation.
if i == 0 {
return false;
}
// Step 2: Reverse the weakly increasing part
self[i..].reverse();
// Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
let mut j = self.len() - 1;
while j >= i && self[j - 1] < self[i - 1] {
j -= 1;
}
// Step 4: Swap that element with the pivot
self.swap(i - 1, j);
true
}
}
//----------------------------------------------------------------------------
// Binary Indexed TreeBIT, Fenwick Tree
#[derive(Clone)]
struct FenwickTree {
n: usize,
data: Vec<i64>,
}
impl FenwickTree {
fn new(n: usize) -> FenwickTree {
FenwickTree {
n: n,
data: vec![0; n + 1],
}
}
// --- sum ---
fn add(&mut self, i: usize, x: i64) {
let mut i = i + 1;
while i <= self.n {
self.data[i] += x;
i += i & i.wrapping_neg();
}
}
fn sum(&self, i: usize) -> i64 {
let mut i = i + 1;
let mut s = 0;
while i > 0 {
s += self.data[i];
i -= i & i.wrapping_neg();
}
s
}
// --- max ---
fn update(&mut self, i: usize, x: i64) {
let mut i = i + 1;
while i <= self.n {
self.data[i] = self.data[i].max(x);
i += i & i.wrapping_neg();
}
}
fn max(&self, i: usize) -> i64 {
let mut i = i + 1;
let mut s = 0;
while i > 0 {
s = s.max(self.data[i]);
i -= i & i.wrapping_neg();
}
s
}
}
//----------------------------------------------------------------------------
struct UnionFind {
n: usize,
parent: Vec<i64>,
}
impl UnionFind {
fn new(n: usize) -> Self {
Self {
n,
parent: vec![-1; n + 1],
}
}
fn root(&mut self, a: usize) -> usize {
if self.parent[a] < 0 {
return a;
}
self.parent[a] = self.root(self.parent[a] as usize) as i64;
return self.parent[a] as usize;
}
fn size(&mut self, a: usize) -> usize {
let r = self.root(a);
return -self.parent[r] as usize;
}
fn connect(&mut self, a: usize, b: usize) -> bool {
let a = self.root(a);
let b = self.root(b);
if a == b {
return false;
}
if self.size(a) > self.size(b) {
self.parent[a] += self.parent[b];
self.parent[b] = a as i64;
} else {
self.parent[b] += self.parent[a];
self.parent[a] = b as i64;
}
return true;
}
}
//----------------------------------------------------------------------------
macro_rules! printvec {
($vec:expr) => {{
print!(
"{}",
$vec.iter()
.map(|&x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
);
}};
}
macro_rules! printvecln {
($vec:expr) => {{
printvec!($vec);
println!();
}};
}
//----------------------------------------------------------------------------
fn main() {
let mut solver = Solver::new();
solver.run();
}
//----------------------------------------------------------------------------
const INF: i64 = 2222222222222222222;
//----------------------------------------------------------------------------
#[derive(Default)]
struct Solver {}
impl Solver {
pub fn new() -> Self {
Self {}
}
pub fn run(&mut self) {
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
self.solve(&mut sc, &mut out);
}
fn solve<W: std::io::Write>(
&mut self,
sc: &mut scanner::Scanner,
out: &mut std::io::BufWriter<W>,
) {
let N: usize = sc.next();
let K: usize = sc.next();
let A: Vec<usize> = sc.next_vec(N);
let mut l = 1;
let mut r = N;
let mut s = 1;
for i in 1..N {
if A[i - 1] < A[i] {
r -= s;
s = 1;
} else if A[i - 1] > A[i] {
l += s;
s = 1;
} else {
s += 1;
}
if K < l || r < K {
let mut ans = Vec::new();
for j in 0..N {
if j != i - 1 {
ans.push(A[j]);
}
}
writeln!(
out,
"{}",
ans.iter()
.map(|&x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
)
.ok();
return;
}
}
let mut ans = Vec::new();
for j in 0..N - 1 {
ans.push(A[j]);
}
writeln!(
out,
"{}",
ans.iter()
.map(|&x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
)
.ok();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0