AtCoder Regular Contest 069

Submission #1670269

Source codeソースコード

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

Task問題 F - Flags
User nameユーザ名 もふ
Created time投稿日時
Language言語 Rust (1.15.1)
Status状態 AC
Score得点 1200
Source lengthソースコード長 6575 Byte
File nameファイル名
Exec time実行時間 2892 ms
Memory usageメモリ使用量 59160 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 1200 / 1200 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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