#684976 (Rust) No.1630 Sorting Integers (Greater than K)

• 問題: No.1630 Sorting Integers (Greater than K)
• ユーザー: cotton_fn_
• 提出日時: 2021-07-31 03:03:00
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 22 ms / 2,000 ms
• コード長: 9,777 bytes
• コンパイル時間: 15,009 ms
• コンパイル使用メモリ: 377,936 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 05:56:52
• 合計ジャッジ時間: 13,903 ms
• ジャッジサーバーID （参考情報）: judge4 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	15 ms; 5,376 KB
testcase_17	AC	20 ms; 5,376 KB
testcase_18	AC	3 ms; 5,376 KB
testcase_19	AC	3 ms; 5,376 KB
testcase_20	AC	21 ms; 5,376 KB
testcase_21	AC	21 ms; 5,376 KB
testcase_22	AC	4 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	22 ms; 5,376 KB
testcase_25	AC	4 ms; 5,376 KB
testcase_26	AC	4 ms; 5,376 KB

ソースコード

#![allow(unused_imports)]
use pio2::*;
use std::{
    collections::*,
    io::{self, prelude::*},
};
fn run<I: Input, O: Write>(mut pin: I, mut out: O) {
    let n: usize = pin.parse();
    let k: Vec<u8> = pin.parse();
    let mut c: Vec<i32> = pin.seq(9).collect();
    c.insert(0, 0);
    if n > k.len() {
        let mut s = vec![];
        for i in 1..=9 {
            for _ in 0..c[i] {
                s.push(i as u8 + b'0');
            }
        }
        out.write_all(&s).unwrap();
        wln!(out);
        return;
    }
    if n < k.len() {
        wln!(out, "-1");
        return;
    }
    let mut i = 0;
    while i < n - 1 {
        let d = (k[i] - b'0') as usize;
        if c[d] == 0 {
            break;
        }
        c[d] -= 1;
        i += 1;
    }
    d!(i);
    let b;
    'outer: loop {
        let d = (k[i] - b'0') as usize;
        for j in d + 1..=9 {
            if c[j] > 0 {
                b = j;
                break 'outer;
            }
        }
        if i == 0 {
            wln!(out, "-1");
            return;
        }
        i -= 1;
        let d = (k[i] - b'0') as usize;
        c[d] += 1;
    }
    d!(i, b);
    out.write_all(&k[..i]).unwrap();
    w!(out, "{}", b);
    c[b] -= 1;
    let mut j = 1;
    while j <= 9 {
        while c[j] > 0 {
            w!(out, "{}", j);
            c[j] -= 1;
        }
        j += 1;
    }
    wln!(out);
}
fn main() {
    let stdin = io::stdin();
    let mut pin = Scanner::new(stdin.lock());
    let stdout = io::stdout();
    let mut out = stdout.lock();
    run(&mut pin, &mut out);
}
pub mod macros {
    #[macro_export]
    macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }
    #[macro_export]
    macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
    #[macro_export]
    macro_rules! w_iter {
        ($dst:expr, $fmt:expr, $iter:expr, $delim:expr) => {{
            let mut first = true;
            for elem in $iter {
                if first {
                    w!($dst, $fmt, elem);
                    first = false;
                } else {
                    w!($dst, concat!($delim, $fmt), elem);
                }
            }
        }};
        ($dst:expr, $fmt:expr, $iter:expr) => {
            w_iter!($dst, $fmt, $iter, " ")
        };
    }
    #[macro_export]
    macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
    #[macro_export]
    macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
    #[macro_export]
    macro_rules ! d { ($ ($ a : expr) ,*) => { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) } ; }
}
pub mod pio2 {
    use std::{
        io::prelude::*,
        marker::PhantomData,
        mem::{self, MaybeUninit},
        str,
    };
    pub trait Input {
        fn bytes(&mut self) -> &[u8];
        fn str(&mut self) -> &str {
            str::from_utf8(self.bytes()).unwrap()
        }
        fn parse<T>(&mut self) -> T
        where
            DefaultParser: Parser<T>,
        {
            self.parse_with(DefaultParser)
        }
        fn parse_with<T, P: Parser<T>>(&mut self, mut parser: P) -> T {
            parser.parse(self)
        }
        fn seq<T>(&mut self, n: usize) -> Seq<Self, T, DefaultParser>
        where
            DefaultParser: Parser<T>,
        {
            self.seq_with(n, DefaultParser)
        }
        fn seq_with<T, P: Parser<T>>(&mut self, n: usize, parser: P) -> Seq<Self, T, P> {
            Seq {
                src: self,
                rest: n,
                parser,
                phantom: PhantomData,
            }
        }
    }
    impl<I: Input> Input for &mut I {
        fn bytes(&mut self) -> &[u8] {
            (**self).bytes()
        }
    }
    pub struct Scanner<R> {
        src: R,
        buf: Vec<u8>,
        pos: usize,
        len: usize,
    }
    impl<R: Read> Scanner<R> {
        pub fn new(src: R) -> Self {
            Self {
                src,
                buf: vec![0; 1 << 16],
                pos: 0,
                len: 0,
            }
        }
        fn read(&mut self) -> usize {
            if self.pos > 0 {
                self.buf.copy_within(self.pos..self.len, 0);
                self.len -= self.pos;
                self.pos = 0;
            } else if self.len >= self.buf.len() {
                self.buf.resize(2 * self.buf.len(), 0);
            }
            let n = self.src.read(&mut self.buf[self.len..]).unwrap();
            self.len += n;
            assert!(self.len <= self.buf.len());
            n
        }
    }
    impl<R: Read> Input for Scanner<R> {
        fn bytes(&mut self) -> &[u8] {
            loop {
                while let Some(d) = unsafe { self.buf.get_unchecked(self.pos..self.len) }
                    .iter()
                    .position(u8::is_ascii_whitespace)
                {
                    let p = self.pos;
                    self.pos += d + 1;
                    if d > 0 {
                        return unsafe { self.buf.get_unchecked(p..p + d) };
                    }
                }
                if self.read() == 0 {
                    let p = self.pos;
                    if p == self.len {
                        panic!("reached EOF");
                    }
                    self.pos = self.len;
                    return unsafe { self.buf.get_unchecked(p..self.len) };
                }
            }
        }
    }
    pub struct Seq<'a, I: ?Sized, T, P> {
        src: &'a mut I,
        rest: usize,
        parser: P,
        phantom: PhantomData<*const T>,
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> Iterator for Seq<'a, I, T, P> {
        type Item = T;
        fn next(&mut self) -> Option<T> {
            if self.rest > 0 {
                self.rest -= 1;
                Some(self.src.parse_with(&mut self.parser))
            } else {
                None
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rest, Some(self.rest))
        }
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> ExactSizeIterator for Seq<'a, I, T, P> {}
    pub trait Parser<T> {
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T;
    }
    impl<T, P: Parser<T>> Parser<T> for &mut P {
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T {
            (*self).parse(src)
        }
    }
    #[derive(Clone, Copy, Debug)]
    pub struct DefaultParser;
    macro_rules! int {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty);
                    let s = src.bytes();
                    if let Some((&b'-', t)) = s.split_first() {
                        -f(t)
                    } else {
                        f(s)
                    }
                }
            }
        };
    }
    int!(isize);
    int!(i8);
    int!(i16);
    int!(i32);
    int!(i64);
    int!(i128);
    macro_rules! uint {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty)
                }
            }
        };
    }
    uint!(usize);
    uint!(u8);
    uint!(u16);
    uint!(u32);
    uint!(u64);
    uint!(u128);
    macro_rules! from_bytes {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().into()
                }
            }
        };
    }
    from_bytes!(Vec<u8>);
    from_bytes!(Box<[u8]>);
    macro_rules! from_str {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.str().parse::<$ty>().expect("failed to parse")
                }
            }
        };
    }
    from_str!(String);
    from_str!(char);
    from_str!(f32);
    from_str!(f64);
    macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T) ,+> Parser < ($ ($ T ,) +) > for DefaultParser where $ (DefaultParser : Parser <$ T >) ,+ { fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> ($ ($ T ,) +) { ($ (< Self as Parser <$ T >>:: parse (self , src) ,) +) } } } ; }
    tuple!(A);
    tuple!(A, B);
    tuple!(A, B, C);
    tuple!(A, B, C, D);
    tuple!(A, B, C, D, E);
    tuple!(A, B, C, D, E, F);
    tuple!(A, B, C, D, E, F, G);
    tuple!(A, B, C, D, E, F, G, H);
    macro_rules ! array { ($ ($ N : literal) *) => { $ (impl < T > Parser < [T ; $ N] > for DefaultParser where DefaultParser : Parser < T > { fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> [T ; $ N] { unsafe { let mut arr : [MaybeUninit < T >; $ N] = MaybeUninit :: uninit () . assume_init () ; for elem in & mut arr { * elem = MaybeUninit :: new (src . parse ()) ; } mem :: transmute_copy (& arr) } } }) * } }
    array ! (1 2 3 4 5 6 7 8);
}