結果
| 問題 |
No.3047 Verification of Sorting Network
|
| ユーザー |
👑  Mizar
|
| 提出日時 | 2025-03-13 04:46:57 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 172 ms / 2,000 ms |
| コード長 | 14,454 bytes |
| コンパイル時間 | 14,111 ms |
| コンパイル使用メモリ | 401,184 KB |
| 実行使用メモリ | 7,324 KB |
| 最終ジャッジ日時 | 2025-03-13 04:47:17 |
| 合計ジャッジ時間 | 19,453 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 61 |
ソースコード
const PROGRESS_THRESHOLD: usize = 28;
const MAX_T: usize = 1000;
const MAX_N: usize = 64;
const MAX_COST: f64 = 1e17;
type State = u64;
// Check if the given comparator network is a sorting network
pub fn is_sorting_network(n: usize, cmp: &[(usize, usize)]) -> Result<Vec<bool>, Vec<bool>> {
// Worst-case time complexity: O(FIB1[n] * (m + n*d))
// m: number of comparators, n: number of input elements, d: depth (layers)
debug_assert!(2 <= n && (n as usize) <= MAX_N && n <= State::BITS as _);
// Ensure 0-indexed and a < b and b < n
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
};
// List of comparators per layer
#[derive(Debug, Clone, Copy)]
struct CeEntry {
cei: usize,
a: usize,
b: usize,
}
#[derive(Debug, Clone, Copy)]
struct CombineEntry {
root_master: usize,
root_slave: usize,
}
#[derive(Debug, Clone)]
enum CmpLayer {
Cmp { root: usize, cmp_part: Vec<CeEntry> },
Combine(CombineEntry),
}
// Construct search processing order
let cmp_layers = {
let mut cmp_layered = vec![false; cmp.len()];
let mut cmp_skip = 0usize;
let mut dsu = DsuBySize::new(n);
let mut layers = vec![];
while cmp_skip < cmp.len() {
let mut layer_checked = vec![false; n];
let mut layer = (0..n).map(|_i| Vec::<CeEntry>::new()).collect::<Vec<_>>();
let mut combine = (usize::MAX, 0, 0);
for (i, &(a, b)) in cmp.iter().enumerate().skip(cmp_skip) {
if cmp_layered[i] {
continue;
}
let checked = layer_checked[a] || layer_checked[b];
layer_checked[a] = true;
layer_checked[b] = true;
if checked {
continue;
}
if dsu.equiv(a, b) {
let (root_a, _) = dsu.root_size(a);
layer[root_a].push(CeEntry { cei: i, a, b });
cmp_layered[i] = true;
} else {
let (root_a, size_a) = dsu.root_size(a);
let (root_b, size_b) = dsu.root_size(b);
combine = combine.min((size_a + size_b, root_a, root_b));
}
}
if layer.iter().all(|v| v.is_empty()) {
let (size, root_a, root_b) = combine;
if size == usize::MAX {
break;
}
dsu.unite(root_a, root_b);
let (root_master, _) = dsu.root_size(root_a);
let root_slave = root_a ^ root_b ^ root_master;
layers.push(CmpLayer::Combine(CombineEntry {
root_master,
root_slave,
}));
} else {
for (root, ces) in layer.iter().enumerate() {
if !ces.is_empty() {
layers.push(CmpLayer::Cmp {
root,
cmp_part: ces.clone(),
});
}
}
for (i, &f) in cmp_layered.iter().enumerate().skip(cmp_skip) {
if f {
cmp_skip = i + 1;
} else {
break;
}
}
}
}
layers
};
// State vector for each input (integrated into the root node of each connection when the connection changes)
let mut states = (0..n)
.map(|i| vec![((1 as State) << i, (1 as State) << i)])
.collect::<Vec<_>>();
// unused[i]: whether the i-th element is used in the sorting network
let mut unused = vec![true; cmp.len()];
// unsorted[i]: whether the i-th and (i+1)-th element pairs may not be sorted
let mut unsorted_i: State = 0;
let mut dsu = DsuBySize::new(n);
for job in cmp_layers {
match job {
CmpLayer::Combine(CombineEntry {
root_master,
root_slave,
}) => {
let (_, size_master) = dsu.root_size(root_master);
let (_, size_slave) = dsu.root_size(root_slave);
dsu.unite(root_master, root_slave);
let (_, size_united) = dsu.root_size(root_master);
let master_len = states[root_master].len();
let slave_len = states[root_slave].len();
let mut united_status =
Vec::with_capacity(states[root_master].len() * states[root_slave].len());
for &(sz, so) in states[root_slave].iter() {
for &(mz, mo) in states[root_master].iter() {
united_status.push((sz | mz, so | mo));
}
}
let united_len = united_status.len();
states[root_slave] = vec![];
states[root_master] = united_status;
if PROGRESS_THRESHOLD <= n {
eprintln!(
"Combining, size: {}+{}=>{}, len: {}*{}=>{}, root_master: {}, root_slave: {}",
size_master,
size_slave,
size_united,
master_len,
slave_len,
united_len,
root_master,
root_slave,
);
}
}
CmpLayer::Cmp { root, cmp_part } => {
let (_, size) = dsu.root_size(root);
let len_pre = states[root].len();
let states_cap = FIB1[size] as usize;
let mut states_next = Vec::with_capacity(states_cap);
let mut stack = Vec::<(usize, State, State)>::with_capacity(states[root].len() + n);
for (mut z, mut o) in states[root].iter() {
for (i, &CeEntry { cei, a, b }) in cmp_part.iter().enumerate() {
if (o >> a) & 1 == 0 || (z >> b) & 1 == 0 {
continue;
} else if (z >> a) & 1 == 0 || (o >> b) & 1 == 0 {
unused[cei] = false;
let (xz, xo) = (((z >> a) ^ (z >> b)) & 1, ((o >> a) ^ (o >> b)) & 1);
z ^= xz << a | xz << b;
o ^= xo << a | xo << b;
} else {
unused[cei] = false;
let (qz, qo) = (z, o & !(1 << a) & !(1 << b));
z &= !(1 << b);
stack.push((i + 1, qz, qo));
}
}
states_next.push((z, o));
}
while let Some((mut i, mut z, mut o)) = stack.pop() {
while let Some(&CeEntry { cei, a, b }) = cmp_part.get(i) {
i += 1;
if (o >> a) & 1 == 0 || (z >> b) & 1 == 0 {
continue;
} else if (z >> a) & 1 == 0 || (o >> b) & 1 == 0 {
unused[cei] = false;
let (xz, xo) = (((z >> a) ^ (z >> b)) & 1, ((o >> a) ^ (o >> b)) & 1);
z ^= xz << a | xz << b;
o ^= xo << a | xo << b;
} else {
unused[cei] = false;
let (qz, qo) = (z, o & !(1 << a) & !(1 << b));
z &= !(1 << b);
stack.push((i, qz, qo));
}
}
states_next.push((z, o));
}
let len_gen = states_next.len();
assert!(len_gen <= states_cap, "n: {}, cmp: {:?}, size: {}, len_pre: {}, states_next.len(): {} <= {}", n, cmp, size, len_pre, len_gen, states_cap);
states_next.sort_unstable();
states_next.dedup();
let len_dedup = states_next.len();
states[root] = states_next;
if PROGRESS_THRESHOLD <= n {
let cmp_tuple = cmp_part
.iter()
.map(|&CeEntry { cei, a, b }| (cei, a, b))
.collect::<Vec<_>>();
eprintln!(
"AppliedCE, size: {}, len: {}=>{}=>{}, root: {}, cmp: {:?}",
size, len_pre, len_gen, len_dedup, root, cmp_tuple
);
}
}
}
}
for queue in states.iter() {
let n1_mask = State::MAX >> (State::BITS - (n - 1) as u32);
let q_mask = queue.first().map(|&(z, o)| z | o).unwrap_or(0);
unsorted_i |= (q_mask & (!q_mask >> 1)) & n1_mask;
for &(z, o) in queue.iter() {
unsorted_i |= o & (z >> 1);
}
}
// All branches are finished
if PROGRESS_THRESHOLD <= n {
eprintln!();
}
// If any branch is not sorted, unsorted_i is non-zero, so it is not a sorting network
if unsorted_i != 0 {
// Return positions that may not be sorted
Err(Vec::from_iter(
(0..n - 1).map(|k| (unsorted_i >> k) & 1 != 0),
))
} else {
// If all branches are sorted, it is a sorting network
// Return unused comparators
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 : golden ratio 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);
// Test case cost <= MAX_COST
assert!(cost <= MAX_COST);
// Read comparators
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 usize, (b - 1) as usize))
.collect::<Vec<_>>();
assert!(cmp.len() == m);
assert!(cmp.iter().all(|&(a, b)| a < b));
// Check if it is a sorting network
match is_sorting_network(n, &cmp) {
Ok(unused) => {
writeln!(&mut bout, "Yes")?;
// List unused comparators 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")?;
// List positions k that may not be sorted
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!("{:.6}[s]", execution_start.elapsed().as_secs_f64());
Ok(())
}
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
}
fn equiv(&mut self, u: usize, v: usize) -> bool {
self.root_size(u).0 == self.root_size(v).0
}
}