Submission #7636925


Source Code Expand

Copy
#![allow(unused_imports, unused_macros, non_snake_case)]
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

//{{{ macros missing in 1.15.1
#[macro_use]
mod macros {
    macro_rules! eprint {
        ($($t:tt)*) => {{
            use ::std::io::Write;
            let _ = write!(::std::io::stderr(), $($t)*);
        }};
    }
    macro_rules! eprintln {
        () => { eprintln!(""); };
        ($($t:tt)*) => {{
            use ::std::io::Write;
            let _ = writeln!(::std::io::stderr(), $($t)*);
        }};
    }
    macro_rules! dbg {
        ($val:expr) => {
            match $val {
                tmp => {
                    eprintln!(
                        "[{}:{}] {} = {:#?}",
                        file!(),
                        line!(),
                        stringify!($val),
                        &tmp
                    );
                    tmp
                }
            }
        };
    }
}
//}}}

fn run() {
    let stdin = std::io::stdin();
    let mut sc = Scanner::new(stdin.lock());
    let n: usize = sc.read();
    let k: usize = sc.read();
    let p: Vec<usize> = sc.read_vec(n);
    let mut bs = BTreeSet::new();
    let mut last_inv = None;
    for i in 0..k {
        bs.insert(p[i]);
        if i + 1 < k && p[i] > p[i + 1] {
            last_inv = Some(i);
        }
    }
    let mut sorted = if last_inv.is_none() { 1 } else { 0 };
    let mut answer = 1;
    for i in k..n {
        let b = i - k;
        let e = i;
        let smallest = bs.iter().next().unwrap().clone();
        let largest = bs.iter().rev().next().unwrap().clone();
        if smallest == p[b] && largest < p[e] {
        } else {
            answer += 1;
        }
        bs.remove(&p[b]);
        bs.insert(p[e]);
        if p[i - 1] > p[i] {
            last_inv = Some(i - 1);
        }
        match last_inv {
            Some(idx) if idx > b => {}
            _ => {
                sorted += 1;
            }
        }
    }
    println!("{}", answer - if sorted >= 2 { sorted - 1 } else { 0 });
}

fn main() {
    std::thread::Builder::new()
        .name("run".to_string())
        .stack_size(1024 * 1024 * 1024)
        .spawn(run)
        .unwrap()
        .join()
        .unwrap()
}

//{{{ Scanner
pub struct Scanner<R> {
    reader: R,
}

impl<R> Scanner<R> {
    pub fn new(r: R) -> Scanner<R> {
        Scanner { reader: r }
    }
}

fn is_whitespace(b: u8) -> bool {
    b == b' ' || b == b'\n' || b == b'\r' || b == b'\t'
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        let buf = std::io::Read::bytes(self.reader.by_ref())
            .map(|b| b.expect("Read failed"))
            .skip_while(|&b| is_whitespace(b))
            .take_while(|&b| !is_whitespace(b))
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error")
    }

    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
//}}}

Submission Info

Submission Time
Task B - Sorting a Segment
User ichyo
Language Rust (1.15.1)
Score 0
Code Size 3250 Byte
Status WA
Exec Time 97 ms
Memory 14716 KB

Compile Error

warning: unknown lint: `unused_macros`, #[warn(unknown_lints)] on by default
 --> ./Main.rs:1:26
  |
1 | #![allow(unused_imports, unused_macros, non_snake_case)]
  |                          ^^^^^^^^^^^^^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 24
WA × 8
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 8572 KB
01-02.txt AC 3 ms 8572 KB
01-03.txt AC 81 ms 8572 KB
01-04.txt AC 72 ms 10620 KB
01-05.txt AC 46 ms 10620 KB
01-06.txt WA 60 ms 10620 KB
01-07.txt WA 61 ms 10620 KB
01-08.txt AC 75 ms 10620 KB
01-09.txt WA 59 ms 10620 KB
01-10.txt WA 63 ms 10620 KB
01-11.txt AC 82 ms 10620 KB
01-12.txt WA 75 ms 10620 KB
01-13.txt AC 76 ms 10620 KB
01-14.txt AC 96 ms 10620 KB
01-15.txt AC 84 ms 10620 KB
01-16.txt AC 87 ms 10620 KB
01-17.txt AC 97 ms 10620 KB
01-18.txt AC 86 ms 10620 KB
01-19.txt AC 86 ms 10620 KB
01-20.txt WA 86 ms 10620 KB
01-21.txt WA 85 ms 12668 KB
01-22.txt AC 95 ms 12668 KB
01-23.txt AC 85 ms 12668 KB
01-24.txt AC 85 ms 12668 KB
01-25.txt WA 83 ms 14716 KB
01-26.txt AC 83 ms 12668 KB
01-27.txt AC 89 ms 12668 KB
01-28.txt AC 83 ms 14716 KB
01-29.txt AC 83 ms 14716 KB
sample-01.txt AC 3 ms 8572 KB
sample-02.txt AC 3 ms 8572 KB
sample-03.txt AC 3 ms 8572 KB