結果

問題 No.3047 Verification of Sorting Network
ユーザー 👑 Mizar
提出日時 2025-02-05 14:48:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,321 ms / 2,000 ms
コード長 5,829 bytes
コンパイル時間 16,504 ms
コンパイル使用メモリ 403,456 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 22:44:06
合計ジャッジ時間 68,816 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

// O(M*2^n) + 512it高速化解
const MAX_T: usize = 10000;
const MAX_N: usize = 27;
const MAX_COST: f64 = 1e8;
type NodeIndex = u8;

// 与えられた比較交換器ネットワークがソーティングネットワークかどうかをチェック
fn is_sorting_network(n: usize, cmp: &[(NodeIndex, NodeIndex)]) -> Result<Vec<bool>, Vec<bool>> {
    const { assert!(MAX_N <= NodeIndex::MAX as _) };
    debug_assert!(2 <= n && (n as usize) <= MAX_N && n <= u32::BITS as _);
    // 0-indexed かつ a < b かつ b < n であることを確認
    let _n = n as NodeIndex;
    debug_assert!(cmp.iter().all(|&(a, b)| a < b && b < _n));
    const LOWS: [u64; 6] = [0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0, 0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000];
    let mut states: [[u64; 8]; MAX_N] = [[0; 8]; MAX_N];
    // unused[i]: i番目の要素がソーティングネットワークで使用されているか
    let mut unused = vec![true; cmp.len()];
    // unsorted[i]: i,(i+1)番目の要素ペアがソートされていない可能性があるか
    let mut unsorted = vec![false; (n - 1) as _];
    for i in 0..(1u64 << n.saturating_sub(9)) {
        for (se, &le) in states.iter_mut().zip(LOWS.iter()) {
            se.fill(le);
        }
        states[6] = [0, u64::MAX, 0, u64::MAX, 0, u64::MAX, 0, u64::MAX];
        states[7] = [0, 0, u64::MAX, u64::MAX, 0, 0, u64::MAX, u64::MAX];
        states[8] = [0, 0, 0, 0, u64::MAX, u64::MAX, u64::MAX, u64::MAX];
        for j in 9..n {
            states[j].fill(((i >> (j - 9)) & 1).wrapping_neg());
        }
        for (j, &(a, b)) in cmp.iter().enumerate() {
            let na: [u64; 8] = std::array::from_fn(|i| states[a as usize][i] & states[b as usize][i]);
            let nb: [u64; 8] = std::array::from_fn(|i| states[a as usize][i] | states[b as usize][i]);
            if states[a as usize] != na {
                states[a as usize] = na;
                states[b as usize] = nb;
                unused[j] = false;
            }
        }
        for (j, se) in states[..n].windows(2).enumerate() {
            if se[0].iter().zip(se[1].iter()).any(|(&a, &b)| (a & !b) != 0) {
                unsorted[j] = 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) as NodeIndex, (b - 1) as NodeIndex)).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(())
}
0