結果
| 問題 |
No.3047 Verification of Sorting Network
|
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-01-26 15:32:09 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 140 ms / 2,000 ms |
| コード長 | 9,826 bytes |
| コンパイル時間 | 12,756 ms |
| コンパイル使用メモリ | 399,548 KB |
| 実行使用メモリ | 7,328 KB |
| 最終ジャッジ日時 | 2025-03-10 03:29:34 |
| 合計ジャッジ時間 | 21,348 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
ソースコード
const MAX_T: usize = 1000;
const MAX_N: usize = 27;
const MAX_COST: f64 = 1e8;
const SHOW_PROGRESS: bool = false;
type NodeIndex = u8;
type CmpIndex = usize;
type State = u64;
// 与えられた比較交換器ネットワークがソーティングネットワークかどうかをチェック
pub fn is_sorting_network(
n: usize,
cmp: &[(NodeIndex, NodeIndex)],
show_progress: bool,
) -> Result<Vec<bool>, Vec<bool>> {
const { assert!(MAX_N <= NodeIndex::MAX as _ && MAX_N * (MAX_N - 1) / 2 <= CmpIndex::MAX as _) };
debug_assert!(2 <= n && (n as usize) <= MAX_N && n <= State::BITS as _);
debug_assert!(cmp.len() <= CmpIndex::MAX as _);
// 0-indexed かつ a < b かつ b < n であることを確認
let _n = n as NodeIndex;
debug_assert!(cmp.iter().all(|&(a, b)| a < b && b < _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
};
// 進捗表示
let (mut progress, mut next_progress) = (0, 0);
fn _show_progress(n: usize, progress: State) -> State {
let p = 100 * progress / FIB1[n];
eprint!("{}%\r", p);
((p + 1) * FIB1[n] - 1) / 100 + 1
}
// スタックに積む要素: 0状態ベクトル z, 1状態ベクトル o, 比較交換器の番号 i
// もし ((z >> j) & 1, (o >> j) & 1) == (1, 1) なら j-bit目の状態は '?'
// もし ((z >> j) & 1, (o >> j) & 1) == (1, 0) なら j-bit目の状態は '0'
// もし ((z >> j) & 1, (o >> j) & 1) == (0, 1) なら j-bit目の状態は '1'
// '0...01...1' または '0...0?1...1' の場合、ソートされている
// 初期状態: 0状態ベクトルは[0,n)-bit目が1、1状態ベクトルは全bitが1、比較交換器の番号は 0
let mut stack = Vec::<(State, State, CmpIndex)>::with_capacity(n as _);
stack.push((State::MAX >> (State::BITS - n as u32), State::MAX, 0));
// unused[i]: i番目の要素がソーティングネットワークで使用されているか
let mut unused = vec![true; cmp.len()];
// unsorted[i]: i,(i+1)番目の要素ペアがソートされていない可能性があるか
let mut unsorted_i: State = 0;
// 非再帰の深さ優先探索による分岐状態の探索
'a: while let Some((mut z, mut o, mut i)) = stack.pop() {
// 比較交換器を順に適用
// 0,1状態ベクトル z,o の a,b-bit目が比較交換器の入出力
while let Some(&(a, b)) = cmp.get(i as usize) {
i += 1;
if (o >> a) & 1 == 0 || (z >> b) & 1 == 0 {
// 比較交換器の入力が ('0', _) or (_, '1') の場合、交換はないので次の比較交換器へ進む
continue;
} else if (z >> a) & 1 != 0 && (o >> b) & 1 != 0 {
// この比較交換器は使用される可能性あり
unused[(i - 1) as usize] = false;
// 比較交換器の入力が ('?', '?') であれば、 ('0', '0') と ('?', '1') に分岐して探索
// 新しい分岐 (qz,qo) は ('?', '?') -> ('0', '0') に遷移
let (qz, mut qo) = (z, o);
qo &= !(1 << a) & !(1 << b);
// 現在の分岐 (z,o) は ('?', '?') -> ('?', '1') に遷移
z &= !(1 << b);
// 新しい分岐の状態 'q' の非0要素の先頭を見つける
if (qo & (qz >> 1)) == 0 {
progress += 1;
if show_progress && progress >= next_progress {
next_progress = _show_progress(n, progress);
}
} else {
// (qz,qo) がソートされていない場合、分岐をスタックに積む
stack.push((qz, qo, i));
}
// (z,o) がソート済みの場合、次の比較交換器へ進む
if (o & (z >> 1)) == 0 {
progress += 1;
if show_progress && progress >= next_progress {
next_progress = _show_progress(n, progress);
}
continue 'a;
}
} else {
// この比較交換器は使用される可能性あり
unused[(i - 1) as usize] = false;
// 比較交換器の入力が ('1', '0') or ('?', '0') or ('1', '?') の場合、要素を交換
let xz = ((z >> a) ^ (z >> b)) & 1;
let xo = ((o >> a) ^ (o >> b)) & 1;
z ^= xz << a | xz << b;
o ^= xo << a | xo << b;
// (z,o) がソート済みの場合、次の比較交換器へ進む
if (o & (z >> 1)) == 0 {
progress += 1;
if show_progress && progress >= next_progress {
next_progress = _show_progress(n, progress);
}
continue 'a;
}
}
}
// この分岐で全ての比較交換が完了し、z,o がソートされていない場合
// ソートされていない位置をマーク
unsorted_i |= o & (z >> 1);
// 進捗加算: 有り得た分岐数=FIB1[残り未知数]
progress += FIB1[(z & o).count_ones() as usize];
if show_progress && progress >= next_progress {
next_progress = _show_progress(n, progress);
}
}
// すべての分岐が終了
if show_progress {
eprintln!();
}
// 進捗が FIB1[n] に達していることを確認
debug_assert!(progress == FIB1[n]);
// いずれかの分岐でソートされていない場合、 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()?;
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 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, SHOW_PROGRESS) {
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(())
}