結果
問題 | No.2732 Similar Permutations |
ユーザー |
|
提出日時 | 2024-11-27 11:50:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 6,771 bytes |
コンパイル時間 | 13,652 ms |
コンパイル使用メモリ | 377,040 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-11-27 11:51:17 |
合計ジャッジ時間 | 28,134 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 101 |
ソースコード
pub use __cargo_equip::prelude::*;use permutohedron::LexicalPermutation;#[allow(unused_imports)]use proconio::{input,marker::{Bytes, Chars, Usize1},};fn main() {input! {n: usize,a: [usize; n],}let m = n.min(10);let mut p = (1..=m).collect::<Vec<_>>();let mut v: Vec<Option<Vec<usize>>> = vec![None; 1 << 19];loop {let mut s = 0;for i in 0..m {s ^= a[i] + p[i];}if let Some(q) = &v[s] {for i in 0..n {print!("{}{}",if i < m { q[i] } else { i + 1 },if i == n - 1 { "\n" } else { " " });}for i in 0..n {print!("{}{}",if i < m { p[i] } else { i + 1 },if i == n - 1 { "\n" } else { " " });}return;} else {v[s] = Some(p.clone());}if !p.next_permutation() {break;}}println!("-1");}// The following code was expanded by `cargo-equip`./// # Bundled libraries////// - `permutohedron 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::permutohedron`////// # License and Copyright Notices////// - `permutohedron 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)`////// ```text/// Copyright (c) 2015-2017 Ulrik Sverdrup "bluss"////// Permission is hereby granted, free of charge, to any/// person obtaining a copy of this software and associated/// documentation files (the "Software"), to deal in the/// Software without restriction, including without/// limitation the rights to use, copy, modify, merge,/// publish, distribute, sublicense, and/or sell copies of/// the Software, and to permit persons to whom the Software/// is furnished to do so, subject to the following/// conditions:////// The above copyright notice and this permission notice/// shall be included in all copies or substantial portions/// of the Software.////// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER/// DEALINGS IN THE SOFTWARE./// ```#[cfg_attr(any(), rustfmt::skip)]#[allow(unused)]mod __cargo_equip {pub(crate) mod crates {pub mod permutohedron {use std::marker::PhantomData;pub use lexical::LexicalPermutation;mod lexical{pub trait LexicalPermutation{fnnext_permutation(&mut self)->bool;fn prev_permutation(&mut self)->bool;}impl<T>LexicalPermutation for[T]where T:Ord{fn next_permutation(&mut self)->bool{if self.len()<2{return false;}let mut i=self.len()-1;while i>0&&self[i-1]>=self[i]{i-=1;}if i==0{return false;}let mutj=self.len()-1;while j>=i&&self[j]<=self[i-1]{j-=1;}self.swap(j,i-1);self[i..].reverse();true}fn prev_permutation(&mut self)->bool{ifself.len()<2{return false;}let mut i=self.len()-1;while i>0&&self[i-1]<=self[i]{i-=1;}if i==0{return false;}self[i..].reverse();let mut j=self.len()-1;while j>=i&&self[j-1]<self[i-1]{j-=1;}self.swap(i-1,j);true}}fn lexical(){let mut data=[1,2,3];data.next_permutation();assert_eq!(&data,&[1,3,2]);data.next_permutation();assert_eq!(&data,&[2,1,3]);data.prev_permutation();assert_eq!(&data,&[1,3,2]);data.prev_permutation();assert_eq!(&data,&[1,2,3]);assert!(!data.prev_permutation());let mut c=0;while data.next_permutation(){c+=1;}assert_eq!(c,5);}}pub mod control{macro_rules!try_control{($e:expr)=>{match$e{x=>if x.should_break(){return x;}}}}#[derive(Copy,Clone,Debug)]pub enum Control<B>{Continue,Break(B),}impl<B>Control<B>{pub fn breaking()->Control<()>{Control::Break(())}pub fnbreak_value(self)->Option<B>{match self{Control::Continue=>None,Control::Break(b)=>Some(b),}}}pub trait ControlFlow{fn continuing()->Self;fn should_break(&self)->bool{false}}impl ControlFlow for(){fn continuing(){}}impl<B>ControlFlow for Control<B>{fn continuing()->Self{Control::Continue}fn should_break(&self)->bool{if let Control::Break(_)=*self{true}else{false}}}impl<E>ControlFlow for Result<(),E>{fn continuing()->Self{Ok(())}fn should_break(&self)->bool{if let Err(_)=*self{true}else{false}}}}use control::ControlFlow;pub fnheap_recursive<T,F,C>(xs:&mut[T],mut f:F)->C where F:FnMut(&mut[T])->C,C:ControlFlow,{match xs.len(){0|1=>f(xs),2=>{try_control!(f(xs));xs.swap(0,1);f(xs)}n=>heap_unrolled_(n,xs,&mut f),}}fn heap_unrolled_<T,F,C>(n:usize,xs:&mut[T],f:&mut F)->C where F:FnMut(&mut[T])->C,C:ControlFlow,{debug_assert!(n>=3);match n{3=>{try_control!(f(xs));xs.swap(0,1);try_control!(f(xs));xs.swap(0,2);try_control!(f(xs));xs.swap(0,1);try_control!(f(xs));xs.swap(0,2);try_control!(f(xs));xs.swap(0,1);f(xs)}n=>{for i in 0..n-1{try_control!(heap_unrolled_(n-1,xs,f));let j=if n%2==0{i}else{0};xs.swap(j,n-1);}heap_unrolled_(n-1,xs,f)}}}pub const MAXHEAP:usize=16;pub struct Heap<'a,Data:'a+?Sized,T:'a>{data:&'a mut Data,n:u32,c:[u8;MAXHEAP-1],_element:PhantomData<&'a mut T>}impl<'a,T,Data:?Sized>Heap<'a,Data,T>where Data:AsMut<[T]>{pub fn new(data:&'a mut Data)->Self{assert!(data.as_mut().len()<=MAXHEAP);Heap{data:data,c:[0;MAXHEAP-1],n:!0,_element:PhantomData,}}pub fn get(&self)->&Data{self.data}pub fn get_mut(&mut self)->&mut Data{self.data}pub fn reset(&mut self){self.n=!0;for cin&mut self.c[..]{*c=0;}}pub fn next_permutation(&mut self)->Option<&mut Data>{if self.n==!0{self.n=0;Some(self.data)}else{while 1+(self.n as usize)<self.data.as_mut().len(){let n=self.n as u8;let nu=self.n as usize;let c=&mut self.c;if c[nu]<=n{let j=if nu%2==0{c[nu]asusize}else{0};self.data.as_mut().swap(j,nu+1);c[nu]+=1;self.n=0;return Some(self.data);}else{c[nu]=0;self.n+=1;}}None}}}impl<'a,Data:?Sized,T>Iterator for Heap<'a,Data,T>where Data:AsMut<[T]>+ToOwned,{type Item=Data::Owned;fn next(&mut self)->Option<Self::Item>{matchself.next_permutation(){None=>None,Some(perm)=>Some(perm.to_owned()),}}}pub fn factorial(n:usize)->usize{(1..n+1).fold(1,|a,b|a*b)}}}pub(crate) mod macros {pub mod permutohedron {}}pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}mod preludes {pub mod permutohedron {}}}