Submission #4070914


Source Code Expand

use std::cmp;
use std::cmp::Ordering;
use std::fmt::Debug;
#[allow(unused_imports)]
use std::fs::File;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Read, Write};
use std::ops::Range;
use std::str::FromStr;

pub fn start<R: Read, W: Write>(input: R, output: &mut W) {
    let mut scanner = Scanner::new(input.bytes().map(Result::unwrap));
    let n = scanner.next_value::<usize>();
    let mut k = scanner.next_value::<usize>();
    let s = scanner.next_bytes();
    let mut buf = s.clone();
    buf.sort();
    let mut s_count = [0; 26];
    for &c in s.iter() {
        s_count[usize::from(c - b'a')] += 1;
    }
    let mut buf_count = s_count.clone();

    let mut result = Vec::new();
    for i in 0..n {
        s_count[usize::from(s[i] - b'a')] -= 1;
        for &c in buf.iter() {
            let t = n
                - i
                - 1
                - (0..26).fold(0, |sum, x| {
                    sum + cmp::min(
                        s_count[x],
                        if usize::from(c - b'a') == x {
                            buf_count[x] - 1
                        } else {
                            buf_count[x]
                        },
                    )
                });
            if k >= t + if c != s[i] { 1 } else { 0 } {
                result.push(c);
                if c != s[i] {
                    k -= 1;
                }
                buf_count[usize::from(c - b'a')] -= 1;
                break;
            }
        }
        let p = buf.binary_search(&result.last().unwrap()).unwrap();
        buf.remove(p);
    }

    writeln!(output, "{}", String::from_utf8(result).unwrap()).unwrap();
}

////////////////////////////
// Snipetts
////////////////////////////

#[allow(dead_code)]
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    let mut out = BufWriter::new(stdout.lock());
    let input = BufReader::new(stdin.lock());
    start(input, &mut out);
}

// // ファイルの場合
// #[allow(dead_code)]
// fn main() {
//     let mut out = BufWriter::new(File::create("output.txt").unwrap());
//     let input = BufReader::new(File::open("input.txt").unwrap());
//     start(input, &mut out);
// }

// 大きなスタックが必要な場合はこちらを利用する
// #[allow(dead_code)]
// fn main() {
//     std::thread::Builder::new()
//         .name("big stack size".into())
//         .stack_size(32 * 1024 * 1024) // 32 MBのスタックサイズ
//         .spawn(|| {
//             let stdin = stdin();
//             let stdout = stdout();
//             let out = BufWriter::new(stdout.lock());
//             let input = BufReader::new(stdin.lock());
//             start(input, out);
//         })
//         .unwrap()
//         .join()
//         .unwrap();
// }

pub struct Scanner<I: Iterator<Item = u8>> {
    input: I,
}

impl<I: Iterator<Item = u8>> Scanner<I> {
    pub fn new(input: I) -> Self {
        Scanner::<I> { input: input }
    }

    // 文字コードはISO/IEC 8859-1 (Latin-1)とする
    pub fn next_value<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        T::from_str(
            &(self
                .input
                .by_ref()
                .map(char::from)
                .skip_while(|x| x.is_whitespace())
                .take_while(|x| !x.is_whitespace())
                .collect::<String>()),
        )
        .unwrap()
    }

    // 文字コードはISO/IEC 8859-1 (Latin-1)とする
    #[allow(dead_code)]
    pub fn next_bytes(&mut self) -> Vec<u8> {
        self.input
            .by_ref()
            .skip_while(|&x| char::from(x).is_whitespace())
            .take_while(|&x| !char::from(x).is_whitespace())
            .collect::<Vec<_>>()
    }

    #[allow(dead_code)]
    pub fn next_array<T: FromStr>(&mut self, len: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..len).map(|_| self.next_value()).collect()
    }

    #[allow(dead_code)]
    pub fn next_2darray<T: FromStr>(&mut self, x: usize, y: usize) -> Vec<Vec<T>>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..y).map(|_| self.next_array(x)).collect()
    }

    #[allow(dead_code)]
    pub fn next_2d_bytes(&mut self, len: usize) -> Vec<Vec<u8>> {
        (0..len).map(|_| self.next_bytes()).collect()
    }
}

// 1.15.1でReverseを使う
// https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Reverse<T>(pub T);

impl<T: PartialOrd> PartialOrd for Reverse<T> {
    fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Reverse<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

// PartialOrdをTotalOrdにするラッパ
// https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

// 順列生成
#[allow(dead_code)]
pub fn permutations<'a, T: 'a + From<u8> + Clone + PartialEq + Sized>(
    n: T,
    k: usize,
) -> Box<Iterator<Item = Vec<T>> + 'a>
where
    Range<T>: Iterator<Item = T>,
{
    fn inner<'a, T: 'a + From<u8> + Clone + PartialEq + Sized>(
        array: Vec<T>,
        depth: usize,
        max: T,
    ) -> Box<Iterator<Item = Vec<T>> + 'a>
    where
        Range<T>: Iterator<Item = T>,
    {
        let na = (T::from(0)..max.clone()).flat_map(move |x| {
            if array.contains(&x) {
                None
            } else {
                let mut newarray = array.clone();
                newarray.push(x);
                Some(newarray)
            }
        });
        if depth > 0 {
            Box::new(na.flat_map(move |x| inner(x, depth - 1, max.clone())))
        } else {
            Box::new(na)
        }
    }
    inner(Vec::new(), k - 1, n)
}

// 組み合わせ生成
#[allow(dead_code)]
pub fn combinations(n: usize, r: usize) -> Box<Iterator<Item = Vec<u8>>> {
    fn inner(
        array: Vec<u8>,
        depth: usize,
        min: usize,
        max: usize,
    ) -> Box<Iterator<Item = Vec<u8>>> {
        let na = (min..(max - depth)).map(move |x| {
            let mut newarray = array.clone();
            newarray.push(x as u8);
            newarray
        });
        if depth > 0 {
            Box::new(na.flat_map(move |x| {
                let next = usize::from(*x.last().unwrap()) + 1;
                inner(x, depth - 1, next, max)
            }))
        } else {
            Box::new(na)
        }
    }
    inner(Vec::new(), r - 1, 0, n)
}

#[derive(Copy)]
struct AhoCorasickState {
    next: [usize; 256],
}

impl Clone for AhoCorasickState {
    fn clone(&self) -> AhoCorasickState {
        AhoCorasickState { next: self.next }
    }
}

impl AhoCorasickState {
    fn new() -> AhoCorasickState {
        AhoCorasickState { next: [0; 256] }
    }

    fn set_next(&mut self, index: usize, value: usize) {
        self.next[index] = value;
    }

    fn get_next(&self, index: usize) -> Option<usize> {
        if self.next[index] != 0 {
            Some(self.next[index])
        } else {
            None
        }
    }

    fn keys(&self) -> Vec<usize> {
        self.next
            .iter()
            .enumerate()
            .filter(|&(_, &y)| y != 0)
            .map(|(y, _)| y)
            .collect::<Vec<_>>()
    }
}

#[allow(dead_code)]
pub struct AhoCorasickAutomaton {
    states: Vec<AhoCorasickState>,
    failure_link: Vec<usize>,
    output: Vec<Vec<Vec<u8>>>,
}

impl AhoCorasickAutomaton {
    pub fn new(terms: &[Vec<u8>]) -> AhoCorasickAutomaton {
        let mut result = AhoCorasickAutomaton {
            states: vec![AhoCorasickState::new()],
            failure_link: Vec::new(),
            output: vec![Vec::new()],
        };
        result.make_trie(terms);
        result.make_failure();
        result
    }

    fn make_trie(&mut self, terms: &[Vec<u8>]) {
        for term in terms {
            let mut current = 0;
            for &c in term {
                let next_key = usize::from(c);
                current = if let Some(next) = self.states[current].get_next(next_key) {
                    next
                } else {
                    let next = self.states.len();
                    self.states.push(AhoCorasickState::new());
                    self.states[current].set_next(next_key, next);
                    self.output.push(Vec::new());
                    next
                };
            }
            self.output[current].push(term.clone());
        }
    }

    fn make_failure(&mut self) {
        let mut failure = vec![0; self.states.len()];
        let mut queue = vec![0];
        while let Some(s) = queue.pop() {
            for x in self.states[s].keys() {
                if let Some(next) = self.g(s, x) {
                    queue.push(next);
                    if s != 0 {
                        let mut f = failure[s];
                        while let None = self.g(f, x) {
                            f = failure[f];
                        }
                        failure[next] = self.g(f, x).unwrap();
                        let mut n = self.output[failure[next]].clone();
                        self.output[next].append(&mut n);
                    }
                }
            }
        }
        self.failure_link = failure;
    }

    fn g(&self, s: usize, x: usize) -> Option<usize> {
        if let Some(r) = self.states[s].get_next(x) {
            Some(r)
        } else if s == 0 {
            Some(0)
        } else {
            None
        }
    }

    pub fn match_iter<'a>(&'a self, query: &'a [u8]) -> AhoCorasickAutomatonMatcher<'a> {
        AhoCorasickAutomatonMatcher {
            index: 0,
            state: 0,
            sindex: 0,
            ac: self,
            query: query,
        }
    }
}

#[derive(Debug, PartialEq, Eq)]
pub struct MatchValue<'a> {
    pub start: usize,
    pub end: usize,
    pub value: &'a [u8],
}

pub struct AhoCorasickAutomatonMatcher<'a> {
    index: usize,
    state: usize,
    sindex: usize,
    ac: &'a AhoCorasickAutomaton,
    query: &'a [u8],
}

impl<'a> Iterator for AhoCorasickAutomatonMatcher<'a> {
    type Item = MatchValue<'a>;

    fn next(&mut self) -> Option<MatchValue<'a>> {
        loop {
            if let Some(r) = self.ac.output[self.state].get(self.sindex) {
                self.sindex += 1;
                return Some(MatchValue {
                    start: self.index - r.len(),
                    end: self.index - 1,
                    value: &r,
                });
            }

            self.sindex = 0;
            if let Some(&c) = self.query.get(self.index) {
                self.index += 1;
                let c = usize::from(c);
                while let None = self.ac.g(self.state, c) {
                    self.state = self.ac.failure_link[self.state];
                }
                self.state = self.ac.g(self.state, c).unwrap();
            } else {
                return None;
            }
        }
    }
}

// Sunday's
pub struct QuickSearchTable {
    table: [usize; 256],
    output: Vec<u8>,
}

impl QuickSearchTable {
    pub fn new(term: &[u8]) -> QuickSearchTable {
        let mut r = [term.len() + 1; 256];
        for (i, &c) in term.iter().enumerate() {
            r[usize::from(c)] = term.len() - i;
        }
        QuickSearchTable {
            table: r,
            output: term.to_vec(),
        }
    }

    pub fn match_iter<'a>(&'a self, query: &'a [u8]) -> QuickSearchMatcher<'a> {
        QuickSearchMatcher {
            index: 0,
            qst: self,
            query: query,
        }
    }
}

pub struct QuickSearchMatcher<'a> {
    index: usize,
    qst: &'a QuickSearchTable,
    query: &'a [u8],
}

impl<'a> Iterator for QuickSearchMatcher<'a> {
    type Item = MatchValue<'a>;

    fn next(&mut self) -> Option<MatchValue<'a>> {
        while self.index + self.qst.output.len() <= self.query.len() {
            let mut j = 0;
            while j < self.qst.output.len() {
                if self.qst.output[j] != self.query[self.index + j] {
                    break;
                }
                j += 1;
            }
            let before_index = self.index;
            self.index += self
                .query
                .get(self.index + self.qst.output.len())
                .and_then(|&x| self.qst.table.get(usize::from(x)))
                .map_or_else(|| self.qst.output.len() + 1, |&x| x);

            if j == self.qst.output.len() {
                return Some(MatchValue {
                    start: before_index,
                    end: before_index + self.qst.output.len() - 1,
                    value: &self.qst.output,
                });
            }
        }
        None
    }
}

#[allow(dead_code)]
pub struct ChainedOrdering(Ordering);

impl ChainedOrdering {
    pub fn then(self, other: Ordering) -> Ordering {
        match self.0 {
            Ordering::Equal => other,
            o => o,
        }
    }

    pub fn and_then<F: FnOnce() -> Ordering>(self, other: F) -> Ordering {
        match self.0 {
            Ordering::Equal => other(),
            o => o,
        }
    }
}

Submission Info

Submission Time
Task C - 辞書式順序ふたたび
User chalharu
Language Rust (1.15.1)
Score 100
Code Size 13407 Byte
Status AC
Exec Time 2 ms
Memory 4352 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 58
Set Name Test Cases
All hand_1_0.txt, hand_1_1.txt, hand_1_2.txt, hand_1_3.txt, hand_1_4.txt, hand_1_5.txt, hand_1_6.txt, hand_1_7.txt, hand_1_8.txt, hand_2_0.txt, hand_2_1.txt, hand_2_10.txt, hand_2_2.txt, hand_2_3.txt, hand_2_4.txt, hand_2_5.txt, hand_2_6.txt, hand_2_7.txt, hand_2_8.txt, hand_2_9.txt, hand_3_2.txt, hand_3_3.txt, hand_3_4.txt, hand_3_5.txt, hand_3_6.txt, hand_4_2.txt, hand_4_3.txt, hand_4_4.txt, hand_4_5.txt, hand_4_6.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt
Case Name Status Exec Time Memory
hand_1_0.txt AC 2 ms 4352 KB
hand_1_1.txt AC 2 ms 4352 KB
hand_1_2.txt AC 2 ms 4352 KB
hand_1_3.txt AC 2 ms 4352 KB
hand_1_4.txt AC 2 ms 4352 KB
hand_1_5.txt AC 2 ms 4352 KB
hand_1_6.txt AC 2 ms 4352 KB
hand_1_7.txt AC 2 ms 4352 KB
hand_1_8.txt AC 2 ms 4352 KB
hand_2_0.txt AC 2 ms 4352 KB
hand_2_1.txt AC 2 ms 4352 KB
hand_2_10.txt AC 2 ms 4352 KB
hand_2_2.txt AC 2 ms 4352 KB
hand_2_3.txt AC 2 ms 4352 KB
hand_2_4.txt AC 2 ms 4352 KB
hand_2_5.txt AC 2 ms 4352 KB
hand_2_6.txt AC 2 ms 4352 KB
hand_2_7.txt AC 2 ms 4352 KB
hand_2_8.txt AC 2 ms 4352 KB
hand_2_9.txt AC 2 ms 4352 KB
hand_3_2.txt AC 2 ms 4352 KB
hand_3_3.txt AC 2 ms 4352 KB
hand_3_4.txt AC 2 ms 4352 KB
hand_3_5.txt AC 2 ms 4352 KB
hand_3_6.txt AC 2 ms 4352 KB
hand_4_2.txt AC 2 ms 4352 KB
hand_4_3.txt AC 2 ms 4352 KB
hand_4_4.txt AC 2 ms 4352 KB
hand_4_5.txt AC 2 ms 4352 KB
hand_4_6.txt AC 2 ms 4352 KB
random_1.txt AC 2 ms 4352 KB
random_10.txt AC 2 ms 4352 KB
random_11.txt AC 2 ms 4352 KB
random_12.txt AC 2 ms 4352 KB
random_13.txt AC 2 ms 4352 KB
random_14.txt AC 2 ms 4352 KB
random_15.txt AC 2 ms 4352 KB
random_2.txt AC 2 ms 4352 KB
random_3.txt AC 2 ms 4352 KB
random_4.txt AC 2 ms 4352 KB
random_5.txt AC 2 ms 4352 KB
random_6.txt AC 2 ms 4352 KB
random_7.txt AC 2 ms 4352 KB
random_8.txt AC 2 ms 4352 KB
random_9.txt AC 2 ms 4352 KB
sample_1.txt AC 2 ms 4352 KB
sample_2.txt AC 2 ms 4352 KB
sample_3.txt AC 2 ms 4352 KB
sample_4.txt AC 2 ms 4352 KB
small_1.txt AC 2 ms 4352 KB
small_2.txt AC 2 ms 4352 KB
small_3.txt AC 2 ms 4352 KB
small_4.txt AC 2 ms 4352 KB
small_5.txt AC 2 ms 4352 KB
small_6.txt AC 2 ms 4352 KB
small_7.txt AC 2 ms 4352 KB
small_8.txt AC 2 ms 4352 KB
small_9.txt AC 2 ms 4352 KB