結果
問題 | No.2210 equence Squence Seuence |
ユーザー |
|
提出日時 | 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 |
ソースコード
#![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]whereT: 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 vectorlet 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 pivotself.swap(j, i - 1);// Step 4: Reverse the (previously) weakly decreasing partself[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 vectorlet 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 partself[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 pivotself.swap(i - 1, j);true}}//----------------------------------------------------------------------------// Binary Indexed Tree(BIT, 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();}}