結果
| 問題 |
No.3047 Verification of Sorting Network
|
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-01-14 23:56:39 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 141 ms / 2,000 ms |
| コード長 | 9,371 bytes |
| コンパイル時間 | 15,598 ms |
| コンパイル使用メモリ | 400,732 KB |
| 実行使用メモリ | 7,324 KB |
| 最終ジャッジ日時 | 2025-03-10 00:10:36 |
| 合計ジャッジ時間 | 24,456 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
ソースコード
const MAX_T: usize = 10000;
const MAX_N: usize = 27;
const MAX_COST: f64 = 1e8;
// 与えられた比較交換器ネットワークがソーティングネットワークかどうかをチェック
fn is_sorting_network(n: usize, cmp: &[(usize, usize)]) -> Result<Vec<bool>, Vec<bool>> {
type NodeIndex = u8;
type CmpIndex = u16;
const { assert!(MAX_N <= NodeIndex::MAX as _ && MAX_N * (MAX_N - 1) / 2 <= CmpIndex::MAX as _) };
assert!(2 <= n && (n as usize) <= MAX_N);
assert!(cmp.len() <= CmpIndex::MAX as _);
// 0-indexed かつ a < b かつ b < n であることを確認
assert!(cmp.iter().all(|&(a, b)| a < b && b < n));
let n = n as NodeIndex;
let cmp_thin = cmp
.iter()
.map(|&(a, b)| (a as NodeIndex, b as NodeIndex))
.collect::<Vec<_>>();
#[derive(Clone, Copy)]
enum State {
Zero, // 0
Unknown, // ?
One, // 1
}
// スタックに積む要素: 状態ベクトル p, 比較交換器の番号 i, pの非0要素の先頭位置 z, pの非1要素の末尾位置 o
// z >= o の場合、p はソートされている (0...01...1 または 0...0?1...1)
let mut stack = Vec::<([State; MAX_N], CmpIndex, NodeIndex, NodeIndex)>::with_capacity(n as _);
// 初期状態: すべての要素は不明(?)、比較交換器の番号は 0、非0要素の先頭位置は 0、非1要素の末尾位置は n-1
stack.push(([State::Unknown; MAX_N], 0, 0, n - 1));
// unused[i]: i番目の要素がソーティングネットワークで使用されているか
let mut unused = vec![true; cmp.len()];
// unsorted[i]: i,(i+1)番目の要素ペアがソートされていない可能性があるか
let mut unsorted = vec![false; (n - 1) as _];
// 非再帰の深さ優先探索による分岐状態の探索
'a: while let Some((mut p, mut i, mut z, mut o)) = stack.pop() {
// 比較交換器を順に適用
while let Some(&(a, b)) = cmp_thin.get(i as usize) {
i += 1;
match (p[a as usize], p[b as usize]) {
(State::Zero, _) | (_, State::One) => {
// 比較交換器の入力が (0, 0) or (1, 1) or (0, 1) or (0, ?) or (?, 1)
// 交換なし、次の比較交換器へ進む
}
(State::Unknown, State::Unknown) => {
// この比較交換器は使用される可能性あり
unused[(i - 1) as usize] = false;
// 比較交換器の入力が (?, ?) であれば、 (0, 0) と (?, 1) に分岐して探索
// 新しい分岐は (0, 0) に遷移
// 現在の分岐は (?, 1) に遷移
let mut q = p.clone();
(q[a as usize], q[b as usize], p[b as usize]) =
(State::Zero, State::Zero, State::One);
// 新しい分岐の状態 'q' の非0要素の先頭を見つける
let mut qz = z;
while qz < o {
if let State::Zero = q[qz as usize] {
qz += 1;
} else {
// 'q' がソートされていない場合、分岐をスタックに積む
stack.push((q, i, qz, o));
break;
}
}
// p がソートされていない場合、p の非1要素の末尾を見つける
while let State::One = p[o as usize] {
o -= 1;
if !(z < o) {
continue 'a;
}
}
}
(State::One, State::Zero)
| (State::Unknown, State::Zero)
| (State::One, State::Unknown) => {
// この比較交換器は使用される可能性あり
unused[(i - 1) as usize] = false;
// 比較交換器の入力が (1, 0) or (?, 0) or (1, ?) の場合、要素を交換
p.swap(a as usize, b as usize);
// p がソートされていない場合、p の非0要素の先頭を見つける
while let State::Zero = p[z as usize] {
z += 1;
if !(z < o) {
continue 'a;
}
}
// p がソートされていない場合、p の非1要素の末尾を見つける
while let State::One = p[o as usize] {
o -= 1;
if !(z < o) {
continue 'a;
}
}
}
}
}
// この分岐で全ての比較交換が完了し、p がソートされていない場合
// ソートされていない位置をマーク
for (i, s) in p[..(n as usize)].windows(2).enumerate() {
match (s[0], s[1]) {
// (0, 0) または (1, 1) または (0, 1) または (0, ?) または (?, 1) の場合
// 操作なし
(State::Zero, _) | (_, State::One) => {}
// (?, ?) または (?, 0) または (1, ?) または (1, 0) の場合
// ソートされていないとマーク
(State::Unknown, State::Unknown)
| (State::Unknown, State::Zero)
| (State::One, State::Unknown)
| (State::One, State::Zero) => {
unsorted[i] = true;
}
}
}
}
// すべての分岐が終了
// いずれかの分岐でソートされていない場合、 unsorted に true が含まれるのでソーティングネットワークではない
if unsorted.iter().any(|&f| f) {
// ソートされていない可能性のある位置を返す
Err(unsorted)
} 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()?;
assert!(t <= MAX_T);
// φ = (1 + √5) / 2 : 黄金数 1.618033988749895
let phi = (1.25f64).sqrt() + 0.5;
let mut cost = 0f64;
for _ in 0..t {
let line = lines.next().unwrap()?;
let mut parts = line.split_whitespace();
let n: usize = parts.next().unwrap().parse()?;
let m: usize = parts.next().unwrap().parse()?;
assert!(2 <= n && (n as usize) <= MAX_N);
assert!(1 <= m && m <= (n as usize) * ((n as usize) - 1) / 2);
cost += m as f64 * phi.powi(n as i32);
// テストケースのコスト <= MAX_COST
assert!(cost <= MAX_COST);
// 比較交換器を読み込む
let va = lines.next().unwrap()?.split_whitespace().map(|s| s.parse::<usize>().unwrap()).collect::<Vec<_>>();
let vb = lines.next().unwrap()?.split_whitespace().map(|s| s.parse::<usize>().unwrap()).collect::<Vec<_>>();
assert_eq!(va.len(), m);
assert_eq!(vb.len(), m);
assert!(va.iter().zip(vb.iter()).all(|(&a, &b)| 1 <= a && a < b && b <= n));
// 1-indexed を 0-indexed に変換
let cmp = va.iter().zip(vb.iter()).map(|(&a, &b)| (a - 1, b - 1)).collect::<Vec<_>>();
// ソーティングネットワークかどうかをチェック
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(())
}