結果
| 問題 |
No.3047 Verification of Sorting Network
|
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-03-11 21:06:21 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 208 ms / 2,000 ms |
| コード長 | 9,062 bytes |
| コンパイル時間 | 13,845 ms |
| コンパイル使用メモリ | 407,464 KB |
| 実行使用メモリ | 7,328 KB |
| 最終ジャッジ日時 | 2025-03-11 21:06:44 |
| 合計ジャッジ時間 | 22,735 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
ソースコード
const PROGRESS_THRESHOLD: usize = 28;
type NodeIndex = usize;
type State = u64;
enum DsuBySizeElement {
Size(usize),
Parent(usize),
}
struct DsuBySize(Vec<DsuBySizeElement>);
impl DsuBySize {
fn new(n: usize) -> Self {
Self((0..n).map(|_| DsuBySizeElement::Size(1)).collect())
}
fn root_size(&mut self, u: usize) -> (usize, usize) {
match self.0[u] {
DsuBySizeElement::Size(size) => (u, size),
DsuBySizeElement::Parent(v) if u == v => (u, 1),
DsuBySizeElement::Parent(v) => {
let (root, size) = self.root_size(v);
self.0[u] = DsuBySizeElement::Parent(root);
(root, size)
}
}
}
fn unite(&mut self, u: usize, v: usize) -> bool {
let (u, size_u) = self.root_size(u);
let (v, size_v) = self.root_size(v);
if u == v {
return false;
}
if size_u < size_v {
self.0[u] = DsuBySizeElement::Parent(v);
self.0[v] = DsuBySizeElement::Size(size_u + size_v);
} else {
self.0[v] = DsuBySizeElement::Parent(u);
self.0[u] = DsuBySizeElement::Size(size_u + size_v);
}
true
}
}
// 与えられた比較交換器ネットワークがソーティングネットワークかどうかをチェック
pub fn is_sorting_network(
n: usize,
cmp: &[(NodeIndex, NodeIndex)],
) -> Result<Vec<bool>, Vec<bool>> {
assert!(2 <= n && n <= State::BITS as usize);
// 0-indexed かつ a < b かつ b < n であることを確認
assert!(cmp.iter().all(|&(a, b)| a < b && b < n as _));
// unused[i]: i番目の要素がソーティングネットワークで使用されているか
let mut unused = Vec::with_capacity(cmp.len());
// unsorted[i]: i,(i+1)番目の要素ペアがソートされていない可能性があるか
let mut unsorted_i: State = 0;
let mut status = (0..n)
.map(|i| vec![((1 as State) << i, (1 as State) << i)])
.collect::<Vec<_>>();
let mut dsu = DsuBySize::new(n);
// Fibonacci numbers: FIB1[0] = 1, FIB1[1] = 1, FIB1[i] = FIB1[i-1] + FIB1[i-2] (2 <= i <= State::BITS)
const FIB1: [State; (State::BITS + 1) as usize] = {
let mut fib = [1; (State::BITS + 1) as usize];
let mut i = 2;
while i <= State::BITS as usize {
fib[i] = fib[i - 1] + fib[i - 2];
i += 1;
}
fib
};
for (i, &(a, b)) in cmp.iter().enumerate() {
let ((root_a, size_a), (root_b, size_b)) = (dsu.root_size(a), dsu.root_size(b));
dsu.unite(a, b);
let (root_master, unite_size) = dsu.root_size(a);
let root_slave = root_a ^ root_b ^ root_master;
let state_reserve = (FIB1[unite_size]).min(if root_a == root_b {
(status[root_a].len() as State) * 2
} else {
(status[root_a].len() as State) * (status[root_b].len() as State) * 2
});
let mut status_next = Vec::with_capacity(state_reserve as usize);
let mut unused_f = true;
let search_len;
if root_a != root_b {
let mut united_status = Vec::with_capacity(status[root_a].len() * status[root_b].len());
for &(sz, so) in status[root_slave].iter() {
for &(mz, mo) in status[root_master].iter() {
united_status.push((sz | mz, so | mo));
}
}
status[root_slave] = Vec::with_capacity(0);
status[root_master] = united_status;
}
search_len = status[root_master].len();
for &(mut z, mut o) in status[root_master].iter() {
if ((o >> a) & 1) == 0 || ((z >> b) & 1) == 0 {
status_next.push((z, o));
} else if ((z >> a) & 1) == 0 || ((o >> b) & 1) == 0 {
unused_f = false;
let xz = ((z >> a) ^ (z >> b)) & 1;
let xo = ((o >> a) ^ (o >> b)) & 1;
z ^= xz << a | xz << b;
o ^= xo << a | xo << b;
status_next.push((z, o));
} else {
unused_f = false;
let (qz, qo) = (z, o & !(1 << a) & !(1 << b));
z &= !(1 << b);
status_next.push((qz, qo));
status_next.push((z, o));
}
}
let gen_len = status_next.len();
assert!(status_next.len() as State <= state_reserve);
unused.push(unused_f);
status_next.sort_unstable();
status_next.dedup();
status[root_master] = status_next;
if PROGRESS_THRESHOLD <= n {
let size_fmt = if root_a != root_b {
format!("({:2},{:2})->{:2}", size_a, size_b, unite_size)
} else {
format!(" ({:2})->{:2}", size_a, unite_size)
};
eprintln!("i: {:3}, ab: ({:2},{:2}), size: {}, search: {}, generate: {}, dedup: {}", i, a, b, size_fmt, search_len, gen_len, status[root_master].len());
}
}
assert!(unused.len() == cmp.len());
for queue in status.iter() {
let n1_mask = State::MAX >> (State::BITS - (n - 1) as u32);
let q_mask = if let Some(&(z, o)) = queue.first() {
z | o
} else {
0
};
unsorted_i |= (q_mask & (!q_mask >> 1)) & n1_mask;
for &(z, o) in queue.iter() {
unsorted_i |= o & (z >> 1);
}
}
if PROGRESS_THRESHOLD <= n {
eprintln!();
}
// いずれかの分岐でソートされていない場合、 unsorted_i が 非0 なのでソーティングネットワークではない
if unsorted_i != 0 {
// ソートされていない可能性のある位置を返す
Err(Vec::from_iter(
(0..n - 1).map(|k| (unsorted_i >> k) & 1 != 0),
))
} else {
// すべての分岐においてソートされたならばソーティングネットワーク
// 未使用の比較交換器を返す
Ok(unused)
}
}
fn main() -> Result<(), Box<dyn std::error::Error>> {
use std::io::Write;
let execution_start = std::time::Instant::now();
let stdin = std::io::stdin();
let mut lines = std::io::BufRead::lines(stdin.lock());
let mut bout = std::io::BufWriter::new(std::io::stdout());
let t: usize = lines.next().unwrap()?.trim().parse()?;
for _ in 0..t {
let line = lines.next().unwrap()?;
let mut parts = line.split_whitespace();
let n: usize = parts.next().unwrap().parse()?;
assert!(2 <= n && n <= State::BITS as usize);
let m: usize = parts.next().unwrap().parse()?;
// 比較交換器を読み込む
let vec_a = lines
.next()
.unwrap()?
.split_whitespace()
.map(|s| s.parse::<usize>().unwrap())
.collect::<Vec<_>>();
let vec_b = lines
.next()
.unwrap()?
.split_whitespace()
.map(|s| s.parse::<usize>().unwrap())
.collect::<Vec<_>>();
assert!(vec_a.len() == m && vec_b.len() == m);
assert!(vec_a.iter().all(|&a| 1 <= a && a <= n));
assert!(vec_b.iter().all(|&b| 1 <= b && b <= n));
let cmp = vec_a
.iter()
.zip(vec_b.iter())
.map(|(&a, &b)| ((a - 1) as NodeIndex, (b - 1) as NodeIndex))
.collect::<Vec<_>>();
assert!(cmp.len() == m);
assert!(cmp.iter().all(|&(a, b)| a < b));
// ソーティングネットワークかどうかをチェック
match is_sorting_network(n, &cmp) {
Ok(unused) => {
writeln!(&mut bout, "Yes")?;
// 未使用の比較交換器 j を列挙
writeln!(&mut bout, "{}", unused.iter().filter(|&&f| f).count())?;
// 1-indexed
writeln!(
&mut bout,
"{}",
unused
.iter()
.enumerate()
.filter_map(|(j, &u)| if u { Some((j + 1).to_string()) } else { None })
.collect::<Vec<_>>()
.join(" ")
)?;
}
Err(unsorted) => {
writeln!(&mut bout, "No")?;
// ソートされていない可能性がある位置 k を列挙
writeln!(&mut bout, "{}", unsorted.iter().filter(|&&f| f).count())?;
// 1-indexed
writeln!(
&mut bout,
"{}",
unsorted
.iter()
.enumerate()
.filter_map(|(k, &u)| if u { Some((k + 1).to_string()) } else { None })
.collect::<Vec<_>>()
.join(" ")
)?;
}
}
}
bout.flush()?;
eprintln!("{} ms", execution_start.elapsed().as_millis());
Ok(())
}