Submission #1670269


Source Code Expand

use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;


fn main(){
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    while let Some(n) = sc.read1() {
        let mut zs = vec![];
        for i in 0..n {
            let x: i64 = sc.read();
            zs.push((x, i));
            let y: i64 = sc.read();
            zs.push((y, i));
        }
        zs.sort();
        let zs = zs;

        let mut n2 = 1;
        while n2 < 2 * n { n2 <<= 1; }

        // perform binary search
        let mut lo = -1;
        let mut hi = 1_000_000_000;
        while hi - lo > 1 {
            let d = (lo + hi) / 2;
            // make 2-SAT instance
            let mut vg = vec![vec![]; 4 * n2];
            let neg = 2 * n2;

            // exactly one flag must be chosen for each (xi, yi)
            let mut pairs = vec![vec![]; n];
            for (j, &(_, i)) in zs.iter().enumerate() {
                pairs[i].push(j);
            }
            for pair in pairs {
                assert_eq!(pair.len(), 2);
                or_clause(&mut vg, n2 + pair[0], n2 + pair[1]);
                or_clause(&mut vg, neg + n2 + pair[0], neg + n2 + pair[1]);
            }

            // implication on parent nodes
            for i in 2..(2 * n2) {
                or_clause(&mut vg, neg + i, i / 2);
            }

            // distance condition
            for i in 0..(2 * n) {
                // min j s.t., |z[j] - z[i]| <= d
                let mut lo = -1;
                let mut hi = i as i32;
                while hi - lo > 1 {
                    let mid = (lo + hi) / 2;
                    if (zs[mid as usize].0 - zs[i].0).abs() <= d {
                        hi = mid;
                    } else {
                        lo = mid;
                    }
                }
                cover(&mut vg, i, hi as usize, i);

                // max j s.t., |z[j] - z[i]| <= d
                let mut lo = i;
                let mut hi = 2 * n;
                while hi - lo > 1 {
                    let mid = (lo + hi) / 2;
                    if (zs[mid].0 - zs[i].0).abs() <= d {
                        lo = mid;
                    } else {
                        hi = mid;
                    }
                }
                cover(&mut vg, i, i + 1, lo + 1);
            }

            // determine if the 2-SAT instance is feasible
            let mut comp = vec![];
            let _ = strongly_connected_components(&mut vg, &mut comp);
            let mut feasible = true;
            for i in 0..(2 * n2) {
                if comp[i] == comp[neg + i] {
                    feasible = false;
                }
            }

            if feasible {
                lo = d;
            } else {
                hi = d;
            }
        }

        println!("{}", hi);
    }
}

fn cover(vg: &mut Vec<Vec<usize>>, i: usize, lo: usize, hi: usize) {
    fn traverse(node_idx: usize,
                node_lp: usize,
                node_rp: usize,
                lo: usize,
                hi: usize,
                i: usize,
                vg: &mut Vec<Vec<usize>>) {
        if node_rp <= lo || hi <= node_lp {
            return;
        }
        if lo <= node_lp && node_rp <= hi {
            let neg = vg.len() / 2;
            let n2 = vg.len() / 4;
            or_clause(vg, neg + n2 + i, neg + node_idx);
            return;
        }

        let node_mp = (node_lp + node_rp) / 2;
        traverse(node_idx * 2 + 0, node_lp, node_mp, lo, hi, i, vg);
        traverse(node_idx * 2 + 1, node_mp, node_rp, lo, hi, i, vg);
    }

    let n2 = vg.len() / 4;
    traverse(1, 0, n2, lo, hi, i, vg);
}

fn or_clause(vg: &mut Vec<Vec<usize>>, x: usize, y: usize) {
    /// 2-SAT clause: (x or y)
    let n = vg.len() / 2;
    //print!("clause:");
    //if x < n { print!(" {}", x); } else { print!(" ~{}", x - n); }
    //if y < n { print!(" {}", y); } else { print!(" ~{}", y - n); }
    //println!();
    let nx = if x < n { x + n } else { x - n };
    let ny = if y < n { y + n } else { y - n };

    vg[nx].push(y);
    vg[ny].push(x);
}

fn strongly_connected_components(vg: &Vec<Vec<usize>>,
                                 component_id: &mut Vec<usize>) -> usize {
    let n = vg.len();
    component_id.resize(n, 0);

    fn dfs1(vg: &Vec<Vec<usize>>,
            idx: usize,
            count: &mut usize,
            visited: &mut Vec<bool>,
            t_order: &mut Vec<usize>) {
        if visited[idx] {
            return;
        }
        visited[idx] = true;
        for &to in &vg[idx] {
            dfs1(vg, to, count, visited, t_order);
        }
        *count -= 1;
        t_order[*count] = idx;
    }

    let mut count = n;
    let mut visited = vec![false; n];
    let mut t_order = vec![0; n];
    for i in 0..n {
        dfs1(vg, i, &mut count, &mut visited, &mut t_order);
    }
    assert_eq!(count, 0);

    // make a new graph with edge directions reversed
    let mut visited = vec![false; n];
    let mut vg_rev = vec![vec![]; n];
    for i in 0..n {
        for &to in &vg[i] {
            vg_rev[to].push(i);
        }
    }

    fn dfs2(vg_rev: &Vec<Vec<usize>>,
            idx: usize,
            count: usize,
            visited: &mut Vec<bool>,
            component_id: &mut Vec<usize>) {
        visited[idx] = true;
        for &from in &vg_rev[idx] {
            if !visited[from] {
                dfs2(vg_rev, from, count, visited, component_id);
            }
        }
        component_id[idx] = count;
    }

    for i in 0..n {
        let j = t_order[i];
        if !visited[j] {
            dfs2(&vg_rev, j, count, &mut visited, component_id);
            count += 1;
        }
    }

    return count;
}

//=============================================================================

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

Submission Info

Submission Time
Task F - Flags
User ir5
Language Rust (1.15.1)
Score 1200
Code Size 6575 Byte
Status AC
Exec Time 2892 ms
Memory 59160 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 30
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 2 ms 4352 KB
00_example_02.txt AC 2 ms 4352 KB
00_example_03.txt AC 3 ms 4352 KB
01.txt AC 38 ms 4476 KB
02.txt AC 16 ms 4352 KB
03.txt AC 5 ms 4352 KB
04.txt AC 8 ms 4352 KB
05.txt AC 8 ms 4352 KB
06.txt AC 1650 ms 45308 KB
07.txt AC 1637 ms 45308 KB
08.txt AC 1640 ms 45308 KB
09.txt AC 36 ms 4476 KB
10.txt AC 16 ms 4352 KB
11.txt AC 5 ms 4352 KB
12.txt AC 8 ms 4352 KB
13.txt AC 8 ms 4352 KB
14.txt AC 1539 ms 45180 KB
15.txt AC 1542 ms 45308 KB
16.txt AC 1526 ms 45180 KB
17.txt AC 40 ms 4476 KB
18.txt AC 18 ms 4352 KB
19.txt AC 1770 ms 45308 KB
20.txt AC 1797 ms 45308 KB
21.txt AC 2266 ms 47356 KB
22.txt AC 2280 ms 47356 KB
23.txt AC 2892 ms 57916 KB
24.txt AC 2367 ms 59040 KB
25.txt AC 2604 ms 59160 KB
26.txt AC 2024 ms 45308 KB
27.txt AC 2 ms 4352 KB