#763708 (Rust) No.1955 Not Prime

• 問題: No.1955 Not Prime
• ユーザー: akakimidori
• 提出日時: 2022-05-20 22:49:40
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 127 ms / 2,000 ms
• コード長: 8,068 bytes
• コンパイル時間: 12,250 ms
• コンパイル使用メモリ: 401,820 KB
• 実行使用メモリ: 26,300 KB
• 最終ジャッジ日時: 2024-09-20 09:10:59
• 合計ジャッジ時間: 14,277 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 26

ソースコード

fn run() {
    input! {
        n: usize,
        p: [(usize, usize); n],
    }
    let m = 1000000;
    let mut is_prime = vec![false; m + 1];
    enumerate_prime(m, |p| is_prime[p] = true);
    let mut sat = SAT2::new(n);
    for (i, &(a, b)) in p.iter().enumerate() {
        for (j, &(c, d)) in p.iter().enumerate() {
            for &(a, x) in [(a, i), (b, !i)].iter() {
                for &(c, y) in [(c, !j), (d, j)].iter() {
                    let v = format!("{}{}", a, c).parse::<usize>().unwrap();
                    if is_prime[v] {
                        sat.either(!x, !y);
                    }
                }
            }
        }
    }
    let ans = sat.solve();
    if ans.is_some() {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    run();
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
// ---------- begin 2-SAT ----------
pub struct SAT2 {
    size: usize,
    clause: Vec<(usize, usize)>,
}

impl SAT2 {
    pub fn new(size: usize) -> Self {
        SAT2 {
            size: size,
            clause: vec![],
        }
    }
    pub fn either(&mut self, a: usize, b: usize) {
        assert!(a.min(!a) < self.size && b.min(!b) < self.size);
        self.clause.push((a, b));
    }
    pub fn add_variable(&mut self) -> usize {
        let v = self.size;
        self.size += 1;
        v
    }
    pub fn at_most_one<V>(&mut self, mut list: V)
    where
        V: Iterator<Item = usize> + Clone,
    {
        let size = list.clone().count();
        if size <= 1 {
            return;
        }
        let mut cur = !list.next().unwrap();
        for v in list.clone().skip(1) {
            let next = self.add_variable();
            self.either(cur, !v);
            self.either(cur, next);
            self.either(!v, next);
            cur = !next;
        }
        self.either(cur, !list.next().unwrap());
    }
    pub fn solve(&self) -> Option<Vec<bool>> {
        let size = self.size;
        let g = CSR::new(
            2 * size,
            self.clause.iter().flat_map(|&(a, b)| {
                let (x, ix) = if a >= size {
                    (!a + size, !a)
                } else {
                    (a, a + size)
                };
                let (y, iy) = if b >= size {
                    (!b + size, !b)
                } else {
                    (b, b + size)
                };
                assert!(x.max(ix).max(y).max(iy) < 2 * size);
                [(ix, y), (iy, x)]
            }),
        );
        let (_, id) = strongly_connected_components(2 * size, |v| g.list(v));
        let mut ans = Vec::with_capacity(size);
        for (a, b) in id.iter().zip(id[size..].iter()) {
            if *a == *b {
                return None;
            } else {
                ans.push(*a > *b);
            }
        }
        Some(ans)
    }
}
// ---------- end 2-SAT ----------
// ---------- begin CSR ----------
pub struct CSR {
    size: usize,
    pos: Vec<u32>,
    list: Vec<u32>,
}

impl CSR {
    pub fn new<I>(size: usize, it: I) -> Self
    where
        I: Iterator<Item = (usize, usize)> + Clone,
    {
        let mut pos = vec![0; size + 1];
        for (s, t) in it.clone() {
            assert!(s < size && t < size);
            pos[s + 1] += 1;
        }
        for i in 1..=size {
            pos[i] += pos[i - 1];
        }
        let mut x = pos[..size].to_vec();
        let mut list = vec![0; pos[size] as usize];
        for (s, t) in it {
            let x = &mut x[s];
            list[*x as usize] = t as u32;
            *x += 1;
        }
        CSR { size, pos, list }
    }
    pub fn list(&self, v: usize) -> impl Iterator<Item = usize> + '_ {
        assert!(v < self.size);
        let s = self.pos[v] as usize;
        let t = self.pos[v + 1] as usize;
        self.list[s..t].iter().map(|p| *p as usize)
    }
}
// ---------- end CSR ----------
// ---------- begin strongry connected components ----------
pub fn strongly_connected_components<G, I>(size: usize, graph: G) -> (usize, Vec<usize>)
where
    G: Fn(usize) -> I,
    I: Iterator<Item = usize>,
{
    let mut ord = vec![0; size];
    let mut res = vec![0; size];
    let mut vertex = vec![];
    let mut dfs = vec![];
    let mut id = 0;
    for s in 0..size {
        if ord[s] > 0 {
            continue;
        }
        vertex.push(s);
        ord[s] = vertex.len();
        dfs.push((s, graph(s)));
        while let Some((v, mut it)) = dfs.pop() {
            (|| {
                while let Some(u) = it.next() {
                    if ord[u] == 0 {
                        vertex.push(u);
                        ord[u] = vertex.len();
                        dfs.push((v, it));
                        dfs.push((u, graph(u)));
                        return;
                    }
                }
                let low = graph(v).map(|u| ord[u]).min().unwrap_or(ord[v]);
                if low < ord[v] {
                    ord[v] = low;
                    return;
                }
                while let Some(u) = vertex.pop() {
                    ord[u] = !0;
                    res[u] = id;
                    if u == v {
                        break;
                    }
                }
                id += 1;
            })();
        }
    }
    res.iter_mut().for_each(|p| *p = id - 1 - *p);
    (id, res)
}
// ---------- end strongry connected components ----------
// ---------- begin enumerate prime ----------
fn enumerate_prime<F>(n: usize, mut f: F)
where
    F: FnMut(usize),
{
    assert!(1 <= n && n <= 5 * 10usize.pow(8));
    let batch = (n as f64).sqrt().ceil() as usize;
    let mut is_prime = vec![true; batch + 1];
    for i in (2..).take_while(|p| p * p <= batch) {
        if is_prime[i] {
            let mut j = i * i;
            while let Some(p) = is_prime.get_mut(j) {
                *p = false;
                j += i;
            }
        }
    }
    let mut prime = vec![];
    for (i, p) in is_prime.iter().enumerate().skip(2) {
        if *p && i <= n {
            f(i);
            prime.push(i);
        }
    }
    let mut l = batch + 1;
    while l <= n {
        let r = std::cmp::min(l + batch, n + 1);
        is_prime.clear();
        is_prime.resize(r - l, true);
        for &p in prime.iter() {
            let mut j = (l + p - 1) / p * p - l;
            while let Some(is_prime) = is_prime.get_mut(j) {
                *is_prime = false;
                j += p;
            }
        }
        for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) {
            f(i + l);
        }
        l += batch;
    }
}
// ---------- end enumerate prime ----------