結果
| 問題 | No.2671 NUPC Decompressor |
| ユーザー |
 tomarint
|
| 提出日時 | 2024-03-15 22:08:56 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 25,346 bytes |
| コンパイル時間 | 13,974 ms |
| コンパイル使用メモリ | 379,256 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-09-30 01:24:34 |
| 合計ジャッジ時間 | 13,693 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_snake_case)]
// use proconio::input;
// use proconio::marker::{Chars, Isize1, Usize1, Bytes};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque, BinaryHeap};
use std::f64::consts::PI;
use std::io::{Read, Write};
use std::mem::swap;
use std::ops::Bound::{Excluded, Included, Unbounded};
use std::cmp::Reverse;
//----------------------------------------------------------------------------
fn read<T: std::str::FromStr>() -> T {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn readvec<T: std::str::FromStr>(n: usize) -> Vec<T> {
(0..n).map(|_| read()).collect()
}
//----------------------------------------------------------------------------
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
//----------------------------------------------------------------------------
macro_rules! chmin {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_min = min!($($cmps),+);
if $base > cmp_min {
$base = cmp_min;
true
} else {
false
}
}};
}
macro_rules! chmax {
($base:expr, $($cmps:expr),+ $(,)*) => {{
let cmp_max = max!($($cmps),+);
if $base < cmp_max {
$base = cmp_max;
true
} else {
false
}
}};
}
macro_rules! min {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::min($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::min($a, min!($($rest),+))
}};
}
macro_rules! max {
($a:expr $(,)*) => {{
$a
}};
($a:expr, $b:expr $(,)*) => {{
std::cmp::max($a, $b)
}};
($a:expr, $($rest:expr),+ $(,)*) => {{
std::cmp::max($a, max!($($rest),+))
}};
}
//----------------------------------------------------------------------------
#[derive(Debug, PartialEq, PartialOrd)]
struct FloatCmp(f64);
impl Eq for FloatCmp {}
impl Ord for FloatCmp {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.0.partial_cmp(&self.0).unwrap()
}
}
//----------------------------------------------------------------------------
// const MOD: i64 = 998_244_353; // 998244353
const MOD: i64 = 1_000_000_007; // 10**9 + 7
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Mint {
val: i64,
}
impl Mint {
pub fn new(n: i64) -> Self {
let mut new_val = n % MOD + MOD;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
pub fn pow(&self, n: i64) -> Self {
if n == 0 {
Self { val: 1 }
} else {
let mut ret = self.pow(n >> 1);
ret *= ret;
if (n & 1) != 0 {
ret *= *self;
}
ret
}
}
pub fn inv(&self) -> Self {
self.pow(MOD - 2)
}
}
impl std::fmt::Display for Mint {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl std::fmt::Debug for Mint {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl std::ops::Add for Mint {
type Output = Self;
fn add(self, other: Self) -> Self::Output {
let mut new_val = self.val + other.val;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
}
impl std::ops::Sub for Mint {
type Output = Self;
fn sub(self, other: Self) -> Self::Output {
let mut new_val = self.val + MOD - other.val;
if new_val >= MOD {
new_val -= MOD;
}
Self { val: new_val }
}
}
impl std::ops::Mul for Mint {
type Output = Self;
fn mul(self, other: Self) -> Self::Output {
Self {
val: (self.val * other.val) % MOD,
}
}
}
impl std::ops::Div for Mint {
type Output = Self;
fn div(self, other: Self) -> Self::Output {
if other.val == 0 {
panic!("0 division occured.");
}
self * other.inv()
}
}
impl std::ops::AddAssign for Mint {
fn add_assign(&mut self, other: Self) {
*self = *self + other;
}
}
impl std::ops::SubAssign for Mint {
fn sub_assign(&mut self, other: Self) {
*self = *self - other;
}
}
impl std::ops::MulAssign for Mint {
fn mul_assign(&mut self, other: Self) {
*self = *self * other;
}
}
impl std::ops::DivAssign for Mint {
fn div_assign(&mut self, other: Self) {
*self = *self / other;
}
}
//----------------------------------------------------------------------------
pub struct MintComb {
fact: Vec<Mint>,
ifact: Vec<Mint>,
}
impl MintComb {
pub fn new(n: usize) -> Self {
let mut obj = Self {
fact: vec![Mint::new(1); n + 1],
ifact: vec![Mint::new(1); n + 1],
};
assert!(n < (MOD as usize));
obj.fact[0] = Mint::new(1);
for i in 1..=n {
obj.fact[i] = obj.fact[i - 1] * Mint::new(i as i64);
}
obj.ifact[n] = obj.fact[n].inv();
for i in (1..=n).rev() {
obj.ifact[i - 1] = obj.ifact[i] * Mint::new(i as i64);
}
obj
}
pub fn permutation(&self, n: usize, k: usize) -> Mint {
if n < k {
Mint::new(0)
} else {
self.fact[n] * self.ifact[n - k]
}
}
pub fn combination(&self, n: usize, k: usize) -> Mint {
if n < k {
Mint::new(0)
} else {
self.fact[n] * self.ifact[k as usize] * self.ifact[n - k]
}
}
}
//----------------------------------------------------------------------------
// 有理数（分数）
#[derive(PartialEq, Debug, Copy, Clone, Eq, PartialOrd, Ord)]
struct Ratio {
numerator: i64, // 分子
denominator: i64, // 分母
}
// ユークリッドの互除法
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
impl std::fmt::Display for Ratio {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
if self.denominator == 1 {
write!(f, "{}", self.numerator)
} else {
write!(f, "{}/{}", self.numerator, self.denominator)
}
}
}
impl Ratio {
fn new(p: i64, q: i64) -> Ratio {
if q == 0 {
panic!("Ratio: divide by zero");
}
let g = gcd(p.abs(), q.abs());
let s = if q < 0 { -1 } else { 1 };
Ratio {
numerator: s * p / g,
denominator: s * q / g,
}
}
fn from_integer(n: i64) -> Ratio {
Ratio {
numerator: n,
denominator: 1,
}
}
fn as_int(&self) -> i64 {
self.numerator / self.denominator
}
fn as_float(&self) -> f64 {
self.numerator as f64 / self.denominator as f64
}
fn numer(&self) -> i64 {
self.numerator
}
fn denom(&self) -> i64 {
self.denominator
}
fn is_integer(&self) -> bool {
self.denominator == 1
}
}
impl std::ops::Add for Ratio {
type Output = Ratio;
fn add(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator + other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Sub for Ratio {
type Output = Ratio;
fn sub(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator - other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Mul for Ratio {
type Output = Ratio;
fn mul(self, other: Ratio) -> Ratio {
let p = self.numerator * other.numerator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl std::ops::Div for Ratio {
type Output = Ratio;
fn div(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator;
let q = self.denominator * other.numerator;
Ratio::new(p, q)
}
}
//----------------------------------------------------------------------------
pub trait BinarySearch<T> {
fn lower_bound(&self, x: &T) -> usize;
fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> BinarySearch<T> for [T] {
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
std::cmp::Ordering::Less => {
low = mid + 1;
}
std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
std::cmp::Ordering::Less | std::cmp::Ordering::Equal => {
low = mid + 1;
}
std::cmp::Ordering::Greater => {
high = mid;
}
}
}
low
}
}
//----------------------------------------------------------------------------
pub trait LexicalPermutation {
/// Return `true` if the slice was permuted, `false` if it is already
/// at the last ordered permutation.
fn next_permutation(&mut self) -> bool;
/// Return `true` if the slice was permuted, `false` if it is already
/// at the first ordered permutation.
fn prev_permutation(&mut self) -> bool;
}
impl<T> LexicalPermutation for [T]
where
T: Ord,
{
/// Original author in Rust: Thomas Backman <serenity@exscape.org>
fn next_permutation(&mut self) -> bool {
// These cases only have 1 permutation each, so we can't do anything.
if self.len() < 2 {
return false;
}
// Step 1: Identify the longest, rightmost weakly decreasing part of the vector
let mut i = self.len() - 1;
while i > 0 && self[i - 1] >= self[i] {
i -= 1;
}
// If that is the entire vector, this is the last-ordered permutation.
if i == 0 {
return false;
}
// Step 2: Find the rightmost element larger than the pivot (i-1)
let mut j = self.len() - 1;
while j >= i && self[j] <= self[i - 1] {
j -= 1;
}
// Step 3: Swap that element with the pivot
self.swap(j, i - 1);
// Step 4: Reverse the (previously) weakly decreasing part
self[i..].reverse();
true
}
fn prev_permutation(&mut self) -> bool {
// These cases only have 1 permutation each, so we can't do anything.
if self.len() < 2 {
return false;
}
// Step 1: Identify the longest, rightmost weakly increasing part of the vector
let mut i = self.len() - 1;
while i > 0 && self[i - 1] <= self[i] {
i -= 1;
}
// If that is the entire vector, this is the first-ordered permutation.
if i == 0 {
return false;
}
// Step 2: Reverse the weakly increasing part
self[i..].reverse();
// Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
let mut j = self.len() - 1;
while j >= i && self[j - 1] < self[i - 1] {
j -= 1;
}
// Step 4: Swap that element with the pivot
self.swap(i - 1, j);
true
}
}
//----------------------------------------------------------------------------
// Binary Indexed Tree（BIT, Fenwick Tree）
#[derive(Clone)]
struct FenwickTree {
n: usize,
data: Vec<i64>,
}
impl FenwickTree {
fn new(n: usize) -> FenwickTree {
FenwickTree {
n: n,
data: vec![0; n + 1],
}
}
// --- sum ---
fn add(&mut self, i: usize, x: i64) {
let mut i = i + 1;
while i <= self.n {
self.data[i] += x;
i += i & i.wrapping_neg();
}
}
fn sum(&self, i: usize) -> i64 {
let mut i = i + 1;
let mut s = 0;
while i > 0 {
s += self.data[i];
i -= i & i.wrapping_neg();
}
s
}
// --- max ---
fn update(&mut self, i: usize, x: i64) {
let mut i = i + 1;
while i <= self.n {
self.data[i] = self.data[i].max(x);
i += i & i.wrapping_neg();
}
}
fn max(&self, i: usize) -> i64 {
let mut i = i + 1;
let mut s = 0;
while i > 0 {
s = s.max(self.data[i]);
i -= i & i.wrapping_neg();
}
s
}
}
//----------------------------------------------------------------------------
// multiset
#[derive(Clone, Debug)]
struct MultiSet<T> {
map: BTreeMap<T, usize>,
len: usize,
}
struct MultiSetIterator<'a, T> {
iter: std::collections::btree_map::Iter<'a, T, usize>,
remaining: usize,
current: Option<&'a T>,
}
impl<'a, T: Ord> Iterator for MultiSetIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.remaining > 0 {
self.remaining -= 1;
self.current
} else {
let (key, count) = self.iter.next()?;
self.current = Some(key);
self.remaining = count - 1;
self.current
}
}
}
impl<'a, T: Ord> DoubleEndedIterator for MultiSetIterator<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.remaining > 0 {
self.remaining -= 1;
self.current
} else {
let (key, count) = self.iter.next_back()?;
self.current = Some(key);
self.remaining = count - 1;
self.current
}
}
}
impl<T: Ord + Clone> MultiSet<T> {
fn new() -> MultiSet<T> {
MultiSet {
map: BTreeMap::new(),
len: 0,
}
}
fn insert(&mut self, value: T) {
*self.map.entry(value.clone()).or_insert(0) += 1;
self.len += 1;
}
fn remove(&mut self, value: &T) -> bool {
if let Some(count) = self.map.get_mut(value) {
if *count > 1 {
*count -= 1;
} else {
self.map.remove(value);
}
self.len -= 1;
true
} else {
false
}
}
fn contains(&self, value: &T) -> bool {
self.map.contains_key(value)
}
fn count(&self, value: &T) -> usize {
*self.map.get(value).unwrap_or(&0)
}
fn is_empty(&self) -> bool {
self.map.is_empty()
}
fn len(&self) -> usize {
self.len
}
fn iter(&self) -> MultiSetIterator<'_, T> {
MultiSetIterator {
iter: self.map.iter(),
remaining: 0,
current: None,
}
}
fn pop_front(&mut self) -> Option<T> {
if self.is_empty() {
return None;
}
let value = self.front().unwrap().clone();
self.remove(&value);
Some(value)
}
fn front(&self) -> Option<&T> {
self.map.iter().next().map(|(key, _)| key)
}
fn pop_back(&mut self) -> Option<T> {
if self.is_empty() {
return None;
}
let value = self.back().unwrap().clone();
self.remove(&value);
Some(value)
}
fn back(&self) -> Option<&T> {
self.map.iter().next_back().map(|(key, _)| key)
}
}
//----------------------------------------------------------------------------
// 区間Set
#[derive(Clone, Debug)]
struct IntervalSet {
st: std::collections::BTreeSet<(i64, i64)>,
}
impl IntervalSet {
fn new() -> Self {
Self {
st: std::collections::BTreeSet::new(),
}
}
// Add [l, r)
fn add(&mut self, kukan: (i64, i64)) {
let mut kukan = kukan;
loop {
let mut rng = self.st.range(kukan..);
if let Some(it) = rng.next() {
if it.0 <= kukan.1 {
kukan.1 = kukan.1.max(it.1);
let it = it.clone();
self.st.remove(&it);
} else {
break;
}
} else {
break;
}
}
loop {
let mut rng = self.st.range(..kukan);
if let Some(it) = rng.next_back() {
if kukan.0 <= it.1 {
kukan.0 = kukan.0.min(it.0);
kukan.1 = kukan.1.max(it.1);
let it = it.clone();
self.st.remove(&it);
} else {
break;
}
} else {
break;
}
}
self.st.insert(kukan);
}
}
//----------------------------------------------------------------------------
struct LazySegmentTree {
n: usize,
val: Vec<i64>,
lazy: Vec<i64>,
}
impl LazySegmentTree {
pub fn new(n: usize) -> Self {
let mut m = 1;
while m < n {
m *= 2;
}
Self {
n: m,
val: vec![0; 2 * m],
lazy: vec![0; 2 * m],
}
}
// k 番目のノードの値を直接 x に更新する
pub fn update_val(&mut self, k: usize, x: i64) {
self.val[self.n + k] = x;
}
// 配列の値を元にセグメント木を構築する
pub fn initialize(&mut self) {
for k in (1..self.n).rev() {
self.val[k] = self.val[2 * k] + self.val[2 * k + 1];
}
}
// k 番目のノードについて遅延評価を行う
pub fn eval(&mut self, k: usize, l: usize, r: usize) {
// 遅延配列が空でない場合、自ノード及び子ノードへの
// 値の伝播が起こる
//@> self.lazy[k] %= (r as i64 - l as i64) * 2;
if self.lazy[k] != 0 {
self.val[k] += self.lazy[k];
//@> self.val[k] = self.lazy[k] - self.val[k];
// 最下段かどうかのチェックをしよう
// 子ノードは親ノードの 1/2 の範囲であるため、
// 伝播させるときは半分にする
if r - l > 1 {
self.lazy[2 * k] += self.lazy[k] / 2;
self.lazy[2 * k + 1] += self.lazy[k] / 2;
}
// 伝播が終わったので、自ノードの遅延配列を空にする
self.lazy[k] = 0;
}
}
// 区間 [a, b) に x を加算する
pub fn add(&mut self, a: usize, b: usize, x: i64) {
self.add_sub(a, b, x, 1, 0, self.n);
}
pub fn add_sub(&mut self, a: usize, b: usize, x: i64, k: usize, l: usize, r: usize) {
// k 番目のノードに対して遅延評価を行う
self.eval(k, l, r);
// 範囲外なら何もしない
if r <= a || b <= l {
return;
}
// 完全に被覆しているならば、遅延配列に値を入れた後に評価
if a <= l && r <= b {
self.lazy[k] += (r as i64 - l as i64) * x;
self.eval(k, l, r);
}
// そうでないならば、子ノードの値を再帰的に計算して、
// 計算済みの値をもらってくる
else {
self.add_sub(a, b, x, 2 * k, l, (l + r) / 2);
self.add_sub(a, b, x, 2 * k + 1, (l + r) / 2, r);
self.val[k] = self.val[2 * k] + self.val[2 * k + 1];
}
}
// 区間 [a, b) の総和を求める
pub fn getsum(&mut self, a: usize, b: usize) -> i64 {
self.getsum_sub(a, b, 1, 0, self.n)
}
pub fn getsum_sub(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> i64 {
if r <= a || b <= l {
return 0;
}
// 関数が呼び出されたら評価！
self.eval(k, l, r);
if a <= l && r <= b {
return self.val[k];
}
let vl = self.getsum_sub(a, b, 2 * k, l, (l + r) / 2);
let vr = self.getsum_sub(a, b, 2 * k + 1, (l + r) / 2, r);
vl + vr
}
}
//----------------------------------------------------------------------------
// トポロジカルソート
fn tsort_dfs(n: usize, to: &Vec<Vec<usize>>, visited: &mut Vec<u8>, result: &mut Vec<usize>) -> bool {
if visited[n] == 1 { // 一時的の印がついている
// 閉路がある
return false;
}
else if visited[n] == 0 { // まだ印がついていない
visited[n] = 1;
for &t in &to[n] {
if !tsort_dfs(t, to, visited, result) {
return false;
}
}
visited[n] = 2;
result.push(n);
}
true
}
fn tsort(n: usize, to: &Vec<Vec<usize>>) -> Vec<usize> {
let mut visited = vec![0u8; n];
let mut result = vec![];
for i in 0..n {
if !tsort_dfs(i, to, &mut visited, &mut result) {
return vec![];
}
}
result.reverse();
result
}
//----------------------------------------------------------------------------
#[derive(Clone)]
struct UnionFind {
n: usize,
parent: Vec<i64>,
}
impl UnionFind {
fn new(n: usize) -> Self {
Self {
n,
parent: vec![-1; n + 1],
}
}
fn root(&mut self, a: usize) -> usize {
if self.parent[a] < 0 {
return a;
}
self.parent[a] = self.root(self.parent[a] as usize) as i64;
return self.parent[a] as usize;
}
fn size(&mut self, a: usize) -> usize {
let r = self.root(a);
return -self.parent[r] as usize;
}
fn connect(&mut self, a: usize, b: usize) -> bool {
let a = self.root(a);
let b = self.root(b);
if a == b {
return false;
}
if self.size(a) > self.size(b) {
self.parent[a] += self.parent[b];
self.parent[b] = a as i64;
} else {
self.parent[b] += self.parent[a];
self.parent[a] = b as i64;
}
return true;
}
fn same(&mut self, a: usize, b: usize) -> bool {
return self.root(a) == self.root(b);
}
}
//----------------------------------------------------------------------------
// Z algorithm
fn z_algorithm(s: &[u8]) -> Vec<usize> {
let slen = s.len();
let mut z = vec![0; slen];
z[0] = slen;
let mut i = 1;
let mut j = 0;
while i < slen {
while i + j < slen && s[j] == s[i + j] {
j += 1;
}
z[i] = j;
if j == 0 {
i += 1;
continue;
}
let mut k = 1;
while k < j && k + z[k] < j {
z[i + k] = z[k];
k += 1;
}
i += k;
j -= k;
}
z
}
//----------------------------------------------------------------------------
macro_rules! printvec {
($vec:expr) => {{
print!(
"{}",
$vec.iter()
.map(|&x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
);
}};
}
macro_rules! printvecln {
($vec:expr) => {{
printvec!($vec);
println!();
}};
}
//----------------------------------------------------------------------------
const INF: i64 = 2222222222222222222;
//----------------------------------------------------------------------------
fn main() {
// let T: usize = read();
let T = 1;
for _ in 0..T {
solve();
}
}
fn solve() {
let nupc = "NUPC".chars().collect::<Vec<_>>();
let mut list = vec![];
list.push(String::from(""));
for i in 0..4 {
let mut newlist = vec![];
for s in &list {
let mut s = s.clone() + &nupc[i].to_string();
newlist.push(s.clone());
s.push_str(&s.clone());
newlist.push(s);
}
list = newlist;
}
list.sort();
let k: usize = read();
println!("{}", list[k - 1]);
}