結果
| 問題 |
No.1630 Sorting Integers (Greater than K)
|
| コンテスト | |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2021-07-31 03:03:00 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 22 |
ソースコード
#![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);
}