結果
| 問題 |
No.3047 Verification of Sorting Network
|
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-02-05 16:17:29 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,134 ms / 2,000 ms |
| コード長 | 7,542 bytes |
| コンパイル時間 | 13,504 ms |
| コンパイル使用メモリ | 400,724 KB |
| 実行使用メモリ | 8,608 KB |
| 最終ジャッジ日時 | 2025-03-05 20:36:52 |
| 合計ジャッジ時間 | 59,436 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
ソースコード
// 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] = Default::default();
// 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 {
let v = ((i >> (j - 9)) & 1).wrapping_neg();
states[j].fill(v);
}
for (j, (a, b)) in cmp
.iter()
.map(|&(a, b)| (usize::from(a), usize::from(b)))
.enumerate()
{
let va = &states[a];
let vb = &states[b];
//let na: [u64; 8] = std::array::from_fn(|i| va[i] & vb[i]);
//let nb: [u64; 8] = std::array::from_fn(|i| va[i] | vb[i]);
//*
#[target_feature(enable = "avx2")]
unsafe fn and_or(va: &[u64; 8], vb: &[u64; 8]) -> ([u64; 8], [u64; 8]) {
use std::arch::x86_64::*;
use std::mem::transmute;
let _va: [__m256i; 2] = transmute(*va);
let _vb: [__m256i; 2] = transmute(*vb);
let (mut _na0, mut _na1): (__m256i, __m256i);
let (mut _nb0, mut _nb1): (__m256i, __m256i);
std::arch::asm!(
"vpand {2}, {0}, {1}",
"vpor {3}, {0}, {1}",
"vpand {6}, {4}, {5}",
"vpor {7}, {4}, {5}",
in(ymm_reg) _va[0], in(ymm_reg) _vb[0], out(ymm_reg) _na0, out(ymm_reg) _nb0,
in(ymm_reg) _va[1], in(ymm_reg) _vb[1], out(ymm_reg) _na1, out(ymm_reg) _nb1,
);
(transmute([_na0, _na1]), transmute([_nb0, _nb1]))
}
let (na, nb) = unsafe { and_or(va, vb) };
// */
/*
let (na, nb): ([u64; 8], [u64; 8]) = unsafe {
use std::arch::x86_64::*;
use std::mem::transmute;
let va: [__m256i; 2] = transmute(*va);
let vb: [__m256i; 2] = transmute(*vb);
(
transmute([_mm256_and_si256(va[0], vb[0]), _mm256_and_si256(va[1], vb[1])]),
transmute([_mm256_or_si256(va[0], vb[0]), _mm256_or_si256(va[1], vb[1])]),
)
};
// */
if *va != na {
states[a] = na;
states[b] = 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(())
}