結果
問題 | No.2671 NUPC Decompressor |
ユーザー |
|
提出日時 | 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; // 998244353const 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]whereT: 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 vectorlet 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 pivotself.swap(j, i - 1);// Step 4: Reverse the (previously) weakly decreasing partself[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 vectorlet 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 partself[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 pivotself.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 algorithmfn 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]);}