結果
問題 |
No.3047 Verification of Sorting Network
|
ユーザー |
![]() |
提出日時 | 2025-03-06 08:20:14 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 467 ms / 2,000 ms |
コード長 | 4,353 bytes |
コンパイル時間 | 14,774 ms |
コンパイル使用メモリ | 401,256 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-06 08:20:58 |
合計ジャッジ時間 | 35,430 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:83:13 | 83 | let mut value = [-1i8; N]; | ----^^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: type alias `Map` is never used --> src/main.rs:57:6 | 57 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:58:6 | 58 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:59:6 | 59 | type Deque<T> = VecDeque<T>; | ^^^^^ warning: creating a shared reference to mutable static is discouraged --> src/main.rs:100:35 | 100 | eprintln!("call: {}", CALL); | ^^^^ shared reference to mutable static | = note: for more information, see <https://doc.rust-lang.org/nightly/edition-guide/rust-2024/static-mut-references.html> = note: shared references to mutable statics are dangerous; it's undefined behavior if the static is mutated or if a mutable reference is created for it while the shared reference lives = note: `#[warn(static_mut_refs)]` on by default
ソースコード
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 } } } // ---------- begin scannner ---------- #[allow(dead_code)] mod scanner { use std::str::FromStr; pub struct Scanner<'a> { it: std::str::SplitWhitespace<'a>, } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace(), } } pub fn next<T: FromStr>(&mut self) -> T { self.it.next().unwrap().parse::<T>().ok().unwrap() } pub fn next_bytes(&mut self) -> Vec<u8> { self.it.next().unwrap().bytes().collect() } pub fn next_chars(&mut self) -> Vec<char> { self.it.next().unwrap().chars().collect() } pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> { (0..len).map(|_| self.next()).collect() } } } // ---------- end scannner ---------- use std::io::Write; use std::collections::*; type Map<K, V> = BTreeMap<K, V>; type Set<T> = BTreeSet<T>; type Deque<T> = VecDeque<T>; fn main() { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut sc = scanner::Scanner::new(&s); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); run(&mut sc, &mut out); } fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) { let t: u32 = sc.next(); for _ in 0..t { let n: usize = sc.next(); let m: usize = sc.next(); let mut p = vec![(N, N); m]; for p in p.iter_mut() { p.0 = sc.next::<usize>() - 1; } for p in p.iter_mut() { p.1 = sc.next::<usize>() - 1; } let mut value = [-1i8; N]; let mut used = vec![false; m]; let mut ban = vec![false; n - 1]; dfs(value, 0, &p, &mut used, &mut ban); use util::*; if ban.iter().any(|b| *b) { writeln!(out, "No").ok(); let b = (1..n).filter(|x| ban[*x - 1]).collect::<Vec<_>>(); writeln!(out, "{}", b.len()).ok(); writeln!(out, "{}", b.iter().join(" ")).ok(); } else { writeln!(out, "Yes").ok(); let b = (0..m).filter(|x| !used[*x]).map(|x| x + 1).collect::<Vec<_>>(); writeln!(out, "{}", b.len()).ok(); writeln!(out, "{}", b.iter().join(" ")).ok(); } unsafe { eprintln!("call: {}", CALL); CALL = 0; } } } const N: usize = 27; static mut CALL: usize = 0; fn dfs(value: [i8; N], po: usize, p: &[(usize, usize)], used: &mut [bool], ban: &mut [bool]) { unsafe { CALL += 1; } if po == p.len() { for i in 0..ban.len() { let l = value[i]; let r = value[i + 1]; ban[i] |= l == 1 && r == 0; ban[i] |= l < 0 && r == 0; ban[i] |= l == 1 && r < 0; ban[i] |= l == -1 && r == -1; } return; } let (x, y) = p[po]; let l = value[x]; let r = value[y]; if l == -1 && r == -1 { let mut v = value; v[x] = 0; v[y] = 0; dfs(v, po + 1, p, used, ban); used[po] = true; v[x] = -1; v[y] = 1; dfs(v, po + 1, p, used, ban); } else if value[x] < 0 { let mut v = value; if v[y] == 0 { used[po] = true; v.swap(x, y); } dfs(v, po + 1, p, used, ban); } else if value[y] < 0 { let mut v = value; if v[x] == 1 { used[po] = true; v.swap(x, y); } dfs(v, po + 1, p, used, ban); } else { let mut v = value; if v[x] > v[y] { used[po] = true; v.swap(x, y); } dfs(v, po + 1, p, used, ban); } }