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 |
|
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 |