QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279959 | #7778. Turning Permutation | ucup-team635# | WA | 0ms | 2116kb | Rust | 5.6kb | 2023-12-09 12:51:58 | 2023-12-09 12:51:58 |
Judging History
answer
fn main() {
input! {
n: usize,
k: u64,
}
let mut binom = vec![vec![T::zero(); n + 1]; n + 1];
for i in 0..=n {
binom[i][0] = T::one();
for j in 1..=i {
binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
}
}
let binom = binom;
let mut dp = vec![vec![], vec![T::one()]];
for n in 2..=n {
let mut next = dp[n - 1].clone();
if n % 2 == 0 {
next.push(T::zero());
for i in (1..next.len()).rev() {
next[i - 1] = next[i - 1] + next[i];
}
} else {
next.insert(0, T::zero());
for i in 1..next.len() {
next[i] = next[i] + next[i - 1];
}
}
dp.push(next);
}
let memo = dp
.iter()
.map(|dp| dp.iter().fold(T::zero(), |s, a| s + *a))
.collect::<Vec<_>>();
let mut p = vec![n; n];
let mut q = vec![n; n];
let mut k = k - 1;
for i in 0..n {
for j in 0..n {
if q[j] < n {
continue;
}
p[i] = j;
q[p[i]] = i;
let mut find = false;
if q.windows(3).all(|q| {
let min = *q.iter().min().unwrap();
let max = *q.iter().max().unwrap();
max == n || (q[1] == min || q[1] == max)
}) {
let mut l = q.iter().position(|q| *q < n).unwrap();
let mut way = memo[l + 1];
let mut cnt = l;
while let Some(r) = ((l + 1)..n).find(|x| q[*x] < n) {
if l + 1 < r && (r - l) % 2 == 1 {
way = T::zero();
break;
}
if l + 1 < r {
way = way * memo[r - l - 1] * binom[r - l - 1 + cnt][cnt];
cnt += r - l - 1;
}
l = r;
}
if l + 1 < n {
way = way * memo[n - l - 1] * binom[n - l - 1 + cnt][cnt];
}
if k >= way.0 {
k -= way.0;
} else {
find = true;
}
}
if find {
break;
} else {
q[p[i]] = n;
p[i] = n;
}
}
if p[i] == n {
println!("-1");
return;
}
}
use util::*;
println!("{}", p.iter().map(|p| *p + 1).join(" "));
}
const UP: u64 = 10u64.pow(18) + 1;
#[derive(Clone, Copy, Debug)]
struct T(u64);
use std::ops::*;
impl T {
fn zero() -> Self {
Self(0)
}
fn one() -> Self {
Self(1)
}
}
impl Add for T {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Self(UP.min(self.0 + rhs.0))
}
}
impl Mul for T {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
Self(UP.min(self.0.saturating_mul(rhs.0)))
}
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
fn chmin(&mut self, x: Self) -> bool;
fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn chmin(&mut self, x: Self) -> bool {
*self > x && {
*self = x;
true
}
}
fn chmax(&mut self, x: Self) -> bool {
*self < x && {
*self = x;
true
}
}
}
// ---------- end chmin, chmax ----------
mod util {
pub trait Join {
fn join(self, sep: &str) -> String;
}
impl<T, I> Join for I
where
I: Iterator<Item = T>,
T: std::fmt::Display,
{
fn join(self, sep: &str) -> String {
let mut s = String::new();
use std::fmt::*;
for (i, v) in self.enumerate() {
if i > 0 {
write!(&mut s, "{}", sep).ok();
}
write!(&mut s, "{}", v).ok();
}
s
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2016kb
input:
3 2
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 2088kb
input:
3 5
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 2116kb
input:
4 6
output:
3 1 2 4
result:
ok 4 number(s): "3 1 2 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 2096kb
input:
4 11
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 2008kb
input:
3 1
output:
-1
result:
wrong answer 1st numbers differ - expected: '1', found: '-1'