結果

問題 No.1311 Reverse Permutation Index
ユーザー cympfh
提出日時 2020-12-09 01:53:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 1,500 ms
コード長 4,107 bytes
コンパイル時間 21,154 ms
コンパイル使用メモリ 382,344 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 23:21:44
合計ジャッジ時間 14,609 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports, unused_macros, dead_code)]
macro_rules! min {
(.. $x:expr) => {{
let mut it = $x.iter();
it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
}};
($x:expr) => ($x);
($x:expr, $($ys:expr),*) => {{
let t = min!($($ys),*);
if $x < t { $x } else { t }
}}
}
macro_rules! max {
(.. $x:expr) => {{
let mut it = $x.iter();
it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
}};
($x:expr) => ($x);
($x:expr, $($ys:expr),*) => {{
let t = max!($($ys),*);
if $x > t { $x } else { t }
}}
}
macro_rules! trace {
($x:expr) => {
#[cfg(debug_assertions)]
eprintln!(">>> {} = {:?}", stringify!($x), $x)
};
($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! flush {
() => {
std::io::stdout().flush().unwrap();
};
}
macro_rules! put {
(.. $x:expr) => {{
let mut it = $x.iter();
if let Some(x) = it.next() { print!("{}", x); }
for x in it { print!(" {}", x); }
println!("");
}};
($x:expr) => { println!("{}", $x) };
($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}
const M: i64 = 1_000_000_007;
// @num/iter/perm
pub struct Permutation {
n: usize,
idx: usize,
}
impl Permutation {
pub fn new(n: usize) -> Permutation {
Permutation { n: n, idx: 0 }
}
pub fn from(mut perm: Vec<usize>) -> Permutation {
let n = perm.len();
let mut idx = 0;
let mut fact = (1..n).fold(1, |prod, x| prod * x);
for i in 0..n {
if i > 0 {
fact /= n - i;
}
idx += perm[i] * fact;
for j in i + 1..n {
if perm[j] > perm[i] {
perm[j] -= 1;
}
}
}
Permutation { n, idx }
}
pub fn to_vec(&self) -> Option<Vec<usize>> {
let mut r = vec![0; self.n];
let mut idx = self.idx;
for k in 1..self.n {
r[k] = idx % (k + 1);
idx /= k + 1;
}
if idx > 0 {
return None;
}
r.reverse();
let mut b = vec![true; self.n];
b[r[0]] = false;
for k in 1..self.n {
let mut count = 0;
for j in 0..self.n {
if b[j] {
if count == r[k] {
r[k] = j;
b[j] = false;
break;
}
count += 1;
}
}
}
Some(r)
}
}
impl Iterator for Permutation {
type Item = Vec<usize>;
fn next(&mut self) -> Option<Vec<usize>> {
let r = self.to_vec();
self.idx += 1;
r
}
}
fn main() {
let mut sc = Scanner::new();
let index: usize = sc.cin();
let n: usize = sc.cin();
let perm = Permutation { n, idx: index };
if let Some(p) = perm.to_vec() {
let mut xs: Vec<_> = p.iter().enumerate().collect();
xs.sort_by_key(|&item| item.1);
let zs: Vec<_> = xs.iter().map(|&item| item.0).collect();
let perm = Permutation::from(zs.clone());
put!(perm.idx);
}
}
use std::collections::VecDeque;
use std::io::{self, Write};
use std::str::FromStr;
struct Scanner {
stdin: io::Stdin,
buffer: VecDeque<String>,
}
impl Scanner {
fn new() -> Self {
Scanner {
stdin: io::stdin(),
buffer: VecDeque::new(),
}
}
fn cin<T: FromStr>(&mut self) -> T {
while self.buffer.is_empty() {
let mut line = String::new();
let _ = self.stdin.read_line(&mut line);
for w in line.split_whitespace() {
self.buffer.push_back(String::from(w));
}
}
self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
}
fn chars(&mut self) -> Vec<char> {
self.cin::<String>().chars().collect()
}
fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.cin()).collect()
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0