結果
問題 | No.1779 Magical Swap |
ユーザー | ikd |
提出日時 | 2021-12-08 23:46:30 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 4,144 bytes |
コンパイル時間 | 19,373 ms |
コンパイル使用メモリ | 383,868 KB |
実行使用メモリ | 9,048 KB |
最終ジャッジ日時 | 2024-07-16 10:58:22 |
合計ジャッジ時間 | 21,057 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 6 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 28 ms
7,952 KB |
testcase_05 | AC | 13 ms
6,940 KB |
testcase_06 | AC | 14 ms
6,940 KB |
testcase_07 | AC | 24 ms
7,212 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 10 ms
6,940 KB |
testcase_10 | AC | 44 ms
8,768 KB |
testcase_11 | AC | 23 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 28 ms
7,140 KB |
testcase_14 | AC | 41 ms
9,048 KB |
testcase_15 | AC | 166 ms
6,944 KB |
testcase_16 | AC | 30 ms
8,936 KB |
testcase_17 | AC | 24 ms
6,944 KB |
testcase_18 | AC | 0 ms
6,944 KB |
ソースコード
//! # Bundled libraries //! //! - `input_i_scanner 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b60dc67706797611e680510aa6492f6397a2e104)` licensed under **missing** as `crate::__cargo_equip::crates::input_i_scanner` //! - `union_find 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b60dc67706797611e680510aa6492f6397a2e104)` licensed under **missing** as `crate::__cargo_equip::crates::union_find` pub use __cargo_equip::prelude::*; use input_i_scanner::InputIScanner; use union_find::UnionFind; fn main() { let stdin = std::io::stdin(); let mut _i_i = InputIScanner::from(stdin.lock()); macro_rules! scan { (($($t: ty),+)) => { ($(scan!($t)),+) }; ($t: ty) => { _i_i.scan::<$t>() as $t }; (($($t: ty),+); $n: expr) => { std::iter::repeat_with(|| scan!(($($t),+))).take($n).collect::<Vec<_>>() }; ($t: ty; $n: expr) => { std::iter::repeat_with(|| scan!($t)).take($n).collect::<Vec<_>>() }; } let t = scan!(usize); for _ in 0..t { let n = scan!(usize); let a = scan!(u32; n); let b = scan!(u32; n); solve(n, a, b); } } fn solve(n: usize, a: Vec<u32>, b: Vec<u32>) { let mut uf = UnionFind::new(n + 1); for i in 2..=n { for j in ((i + i)..=n).step_by(i) { uf.unite(i, j); } } let mut c = vec![vec![]; n + 1]; for i in 1..=n { let p = uf.find(i); c[p].push(i); } for i in 1..=n { if c[i].is_empty() { continue; } let mut a: Vec<u32> = c[i].iter().copied().map(|j| a[j - 1]).collect(); let mut b: Vec<u32> = c[i].iter().copied().map(|j| b[j - 1]).collect(); a.sort(); b.sort(); if a != b { println!("No"); return; } } println!("Yes"); } // The following code was expanded by `cargo-equip`. #[rustfmt::skip] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod input_i_scanner {use std::fmt;use std::io;use std::str;pub struct InputIScanner<R>{r:R,l:String,i:usize,}impl<R:io::BufRead>InputIScanner<R>{pub fn new(reader:R)->Self{Self{r:reader,l:String::new(),i:0,}}pub fn scan<T>(&mut self)->T where T:str::FromStr,<T as str::FromStr>::Err:fmt::Debug,{self.skip_blanks();assert!(self.i<self.l.len());assert_ne!(&self.l[self.i..=self.i]," ");let rest=&self.l[self.i..];let len=rest.find(' ').unwrap_or_else(| |rest.len());let val=rest[..len].parse().unwrap_or_else(|e|panic!("{:?}, attempt to read `{}`",e,rest));self.i+=len;val}fn skip_blanks(&mut self){loop{match self.l[self.i..].find(|ch|ch!=' '){Some(j)=>{self.i+=j;break;}None=>{let mut buf=String::new();let num_bytes=self.r.read_line(&mut buf).unwrap_or_else(|_|panic!("invalid UTF-8"));assert!(num_bytes>0,"reached EOF :(");self.l=buf.trim_end_matches('\n').trim_end_matches('\r').to_string();self.i=0;}}}}}impl<'a>From<&'a str>for InputIScanner<&'a[u8]>{fn from(s:&'a str)->Self{Self::new(s.as_bytes())}}impl<'a>From<io::StdinLock<'a> >for InputIScanner<io::BufReader<io::StdinLock<'a> > >{fn from(stdin:io::StdinLock<'a>)->Self{Self::new(io::BufReader::new(stdin))}}} pub mod union_find {pub struct UnionFind{par:Vec<usize>,size:Vec<usize>,}impl UnionFind{pub fn new(n:usize)->UnionFind{UnionFind{par:(0..n).collect(),size:vec![1;n],}}pub fn find(&mut self,i:usize)->usize{if self.par[i]!=i{self.par[i]=self.find(self.par[i]);}self.par[i]}pub fn unite(&mut self,i:usize,j:usize){let i=self.find(i);let j=self.find(j);if i==j{return;}let(i,j)=if self.size[i]>=self.size[j]{(i,j)}else{(j,i)};self.par[j]=i;self.size[i]+=self.size[j];}pub fn get_size(&mut self,i:usize)->usize{let p=self.find(i);self.size[p]}pub fn same(&mut self,i:usize,j:usize)->bool{self.find(i)==self.find(j)}}} } pub(crate) mod macros { pub mod input_i_scanner {} pub mod union_find {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod input_i_scanner {} pub mod union_find {} } }