結果
問題 | No.1311 Reverse Permutation Index |
ユーザー |
|
提出日時 | 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 |
ソースコード
#![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/permpub 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()}}