結果
| 問題 | No.1955 Not Prime |
| ユーザー |
 manta1130
|
| 提出日時 | 2022-05-21 00:07:27 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 722 ms / 2,000 ms |
| コード長 | 23,423 bytes |
| コンパイル時間 | 2,451 ms |
| コンパイル使用メモリ | 207,788 KB |
| 実行使用メモリ | 63,956 KB |
| 最終ジャッジ日時 | 2023-10-20 15:02:29 |
| 合計ジャッジ時間 | 10,830 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 70 ms
18,492 KB |
| testcase_01 | AC | 68 ms
18,488 KB |
| testcase_02 | AC | 68 ms
18,488 KB |
| testcase_03 | AC | 67 ms
18,488 KB |
| testcase_04 | AC | 68 ms
18,488 KB |
| testcase_05 | AC | 65 ms
18,488 KB |
| testcase_06 | AC | 96 ms
18,504 KB |
| testcase_07 | AC | 472 ms
18,612 KB |
| testcase_08 | AC | 412 ms
18,612 KB |
| testcase_09 | AC | 714 ms
18,616 KB |
| testcase_10 | AC | 461 ms
18,616 KB |
| testcase_11 | AC | 437 ms
63,956 KB |
| testcase_12 | AC | 245 ms
18,612 KB |
| testcase_13 | AC | 722 ms
19,040 KB |
| testcase_14 | AC | 167 ms
18,524 KB |
| testcase_15 | AC | 159 ms
18,524 KB |
| testcase_16 | AC | 315 ms
18,612 KB |
| testcase_17 | AC | 570 ms
20,092 KB |
| testcase_18 | AC | 717 ms
18,616 KB |
| testcase_19 | AC | 639 ms
28,556 KB |
| testcase_20 | AC | 67 ms
18,492 KB |
| testcase_21 | AC | 265 ms
18,612 KB |
| testcase_22 | AC | 65 ms
18,492 KB |
| testcase_23 | AC | 68 ms
18,492 KB |
| testcase_24 | AC | 66 ms
18,492 KB |
| testcase_25 | AC | 66 ms
18,488 KB |
ソースコード
#[allow(unused_imports)]
use std::io::{stdout, BufWriter, Write};
fn main() {
let out = stdout();
let mut out = BufWriter::new(out.lock());
inputv! {
n:usize,
}
let mut v = vec![];
let mut w = vec![];
for _ in 0..n {
inputv! {
a:String,b:String,
}
v.push(a);
w.push(b);
}
let mut t = TwoSat::new(n);
let pl = get_primelist(10_000_000);
for i in 0..n {
for j in 0..n {
let mut p = true;
let num = v[i]
.chars()
.chain(w[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[i]
.chars()
.chain(w[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[j]
.chars()
.chain(w[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[j]
.chars()
.chain(w[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
if !p {
t.add_clause(i, false, j, false);
}
let mut p = true;
let num = v[i]
.chars()
.chain(w[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[i]
.chars()
.chain(v[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[j]
.chars()
.chain(w[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[j]
.chars()
.chain(v[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
if !p {
t.add_clause(i, false, j, true);
}
let mut p = true;
let num = w[i]
.chars()
.chain(v[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[i]
.chars()
.chain(w[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[j]
.chars()
.chain(v[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = v[j]
.chars()
.chain(w[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
if !p {
t.add_clause(i, true, j, false);
}
let mut p = true;
let num = w[i]
.chars()
.chain(v[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[i]
.chars()
.chain(v[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[j]
.chars()
.chain(v[i].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
let num = w[j]
.chars()
.chain(v[j].chars())
.collect::<String>()
.parse::<u64>()
.unwrap();
p &= !pl.binary_search(&num).is_ok();
if !p {
t.add_clause(i, true, j, true);
}
}
}
writeln!(out, "{}", if t.satisfiable() { "Yes" } else { "No" }).unwrap();
//let ans = t.answer();
//dbg!(ans);
}
//https://github.com/rust-lang-ja/ac-library-rs
//https://github.com/manta1130/competitive-template-rs
use input::*;
use primenumber::*;
use twosat::*;
pub mod input {
use std::cell::RefCell;
use std::io;
pub const SPLIT_DELIMITER: char = ' ';
pub use std::io::prelude::*;
thread_local! {
pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
}
#[macro_export]
macro_rules! input_internal {
($x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
while p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.filter(|q| q.len() > 0)
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let $x: $t = buf_split_result.parse().unwrap();
};
(mut $x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
while p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.filter(|q| q.len() > 0)
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let mut $x: $t = buf_split_result.parse().unwrap();
};
}
pub fn input_buffer_is_empty() -> bool {
let mut empty = false;
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
empty = true;
}
});
empty
}
#[macro_export]
macro_rules! inputv {
($i:ident : $t:ty) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty) => {
input_internal!{mut $i : $t}
};
($i:ident : $t:ty $(,)*) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty $(,)*) => {
input_internal!{mut $i : $t}
};
(mut $i:ident : $t:ty,$($q:tt)*) => {
input_internal!{mut $i : $t}
inputv!{$($q)*}
};
($i:ident : $t:ty,$($q:tt)*) => {
input_internal!{$i : $t}
inputv!{$($q)*}
};
}
pub fn input_all() {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let mut temp_str = String::new();
std::io::stdin().read_to_string(&mut temp_str).unwrap();
let mut split_result_iter = temp_str
.split_whitespace()
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
}
pub fn input_line_str() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).unwrap();
s.trim().to_string()
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector<T>() -> Vec<T>
where
T: std::str::FromStr,
{
let mut v: Vec<T> = Vec::new();
let s = input_line_str();
let split_result = s.split(SPLIT_DELIMITER);
for z in split_result {
let buf = match z.parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector_row<T>(n: usize) -> Vec<T>
where
T: std::str::FromStr,
{
let mut v = Vec::with_capacity(n);
for _ in 0..n {
let buf = match input_line_str().parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
pub trait ToCharVec {
fn to_charvec(&self) -> Vec<char>;
}
impl ToCharVec for String {
fn to_charvec(&self) -> Vec<char> {
self.to_string().chars().collect::<Vec<_>>()
}
}
}
pub mod internal_scc {
pub struct Csr<E> {
start: Vec<usize>,
elist: Vec<E>,
}
impl<E> Csr<E>
where
E: Copy,
{
pub fn new(n: usize, edges: &[(usize, E)], init: E) -> Self {
let mut csr = Csr {
start: vec![0; n + 1],
elist: vec![init; edges.len()],
};
for e in edges.iter() {
csr.start[e.0 + 1] += 1;
}
for i in 1..=n {
csr.start[i] += csr.start[i - 1];
}
let mut counter = csr.start.clone();
for e in edges.iter() {
csr.elist[counter[e.0]] = e.1;
counter[e.0] += 1;
}
csr
}
}
#[derive(Copy, Clone)]
struct _Edge {
to: usize,
}
pub struct SccGraph {
n: usize,
edges: Vec<(usize, _Edge)>,
}
impl SccGraph {
pub fn new(n: usize) -> Self {
SccGraph { n, edges: vec![] }
}
pub fn num_vertices(&self) -> usize {
self.n
}
pub fn add_edge(&mut self, from: usize, to: usize) {
self.edges.push((from, _Edge { to }));
}
pub fn scc_ids(&self) -> (usize, Vec<usize>) {
struct _Env {
g: Csr<_Edge>,
now_ord: usize,
group_num: usize,
visited: Vec<usize>,
low: Vec<usize>,
ord: Vec<Option<usize>>,
ids: Vec<usize>,
}
let mut env = _Env {
g: Csr::new(self.n, &self.edges, _Edge { to: 0 }),
now_ord: 0,
group_num: 0,
visited: Vec::with_capacity(self.n),
low: vec![0; self.n],
ord: vec![None; self.n],
ids: vec![0; self.n],
};
fn dfs(v: usize, n: usize, env: &mut _Env) {
env.low[v] = env.now_ord;
env.ord[v] = Some(env.now_ord);
env.now_ord += 1;
env.visited.push(v);
for i in env.g.start[v]..env.g.start[v + 1] {
let to = env.g.elist[i].to;
if let Some(x) = env.ord[to] {
env.low[v] = std::cmp::min(env.low[v], x);
} else {
dfs(to, n, env);
env.low[v] = std::cmp::min(env.low[v], env.low[to]);
}
}
if env.low[v] == env.ord[v].unwrap() {
loop {
let u = *env.visited.last().unwrap();
env.visited.pop();
env.ord[u] = Some(n);
env.ids[u] = env.group_num;
if u == v {
break;
}
}
env.group_num += 1;
}
}
for i in 0..self.n {
if env.ord[i].is_none() {
dfs(i, self.n, &mut env);
}
}
for x in env.ids.iter_mut() {
*x = env.group_num - 1 - *x;
}
(env.group_num, env.ids)
}
#[allow(clippy::redundant_closure)]
pub fn scc(&self) -> Vec<Vec<usize>> {
let ids = self.scc_ids();
let group_num = ids.0;
let mut counts = vec![0usize; group_num];
for &x in ids.1.iter() {
counts[x] += 1;
}
let mut groups: Vec<Vec<usize>> = (0..ids.0).map(|_| vec![]).collect();
for i in 0..group_num {
groups[i].reserve(counts[i]);
}
for i in 0..self.n {
groups[ids.1[i]].push(i);
}
groups
}
}
}
pub mod primenumber {
use std::iter::Iterator;
type ValueType = u64;
pub trait GetDivisor {
fn get_divisor(&self) -> Divisor;
}
macro_rules! GetDivisor_macro{
($($t:ty),*) => {
$(
impl GetDivisor for $t {
fn get_divisor(&self) -> Divisor {
Divisor::calc(*self as ValueType)
}
})*
};
}
GetDivisor_macro!(u32, u64, u128, usize, i32, i64, i128, isize);
pub trait GetPrimeFactorization {
fn prime_factorization(&self) -> PrimeFactorization;
}
macro_rules! PrimeFactorization_macro{
($($t:ty),*) => {
$(
impl GetPrimeFactorization for $t {
fn prime_factorization(&self) -> PrimeFactorization {
PrimeFactorization::calc(*self as ValueType)
}
})*
};
}
PrimeFactorization_macro!(u32, u64, u128, usize, i32, i64, i128, isize);
pub struct Divisor {
n: ValueType,
cur: ValueType,
flag: bool,
}
impl Divisor {
pub fn calc(n: ValueType) -> Divisor {
Divisor {
n,
cur: 1,
flag: false,
}
}
}
impl Iterator for Divisor {
type Item = ValueType;
fn next(&mut self) -> Option<Self::Item> {
if self.cur * self.cur > self.n {
None
} else if self.flag {
if self.cur * self.cur == self.n {
return None;
}
self.flag = false;
self.cur += 1;
Some(self.n / (self.cur - 1))
} else {
while self.n % self.cur != 0 {
self.cur += 1;
if self.cur * self.cur > self.n {
return None;
}
}
self.flag = true;
Some(self.cur)
}
}
}
pub struct PrimeFactorization<'a> {
n: ValueType,
cur: ValueType,
p_list: Option<&'a [ValueType]>,
idx: usize,
}
impl<'a> PrimeFactorization<'a> {
pub fn calc(n: ValueType) -> PrimeFactorization<'a> {
PrimeFactorization {
n,
cur: 1,
p_list: None,
idx: 0,
}
}
pub fn calc_fast(n: ValueType, p_list: &'a [ValueType]) -> PrimeFactorization<'a> {
PrimeFactorization {
n,
cur: 1,
p_list: Some(p_list),
idx: 0,
}
}
}
impl<'a> Iterator for PrimeFactorization<'a> {
type Item = ValueType;
fn next(&mut self) -> Option<Self::Item> {
loop {
if self.cur == 0 || self.cur > self.n {
return None;
}
if self.p_list.is_some() {
if self.idx >= self.p_list.unwrap().len() {
return None;
}
self.cur = self.p_list.unwrap()[self.idx];
self.idx += 1;
} else {
self.cur += 1;
}
if self.cur * self.cur > self.n {
if self.n != 1 {
self.cur = 0;
return Some(self.n);
}
return None;
}
if self.n % self.cur == 0 {
self.n /= self.cur;
if self.p_list.is_some() {
self.idx -= 1;
}
self.cur -= 1;
return Some(self.cur + 1);
}
}
}
}
pub fn get_primelist(u: ValueType) -> Vec<ValueType> {
let mut v = vec![true; u as usize + 1];
let mut r = vec![];
for i in 2..=u as usize {
if v[i] {
r.push(i as ValueType);
let mut j = i * i;
while j <= u as usize {
v[j] = false;
j += i;
}
}
}
r
}
pub fn get_mobius(n: ValueType) -> Vec<isize> {
let mut r = vec![0, 1];
let p = get_primelist(n);
for i in 2..=n {
let mut f = PrimeFactorization::calc_fast(i as u64, &p).collect::<Vec<_>>();
let count = f.len();
f.dedup();
if f.len() != count {
r.push(0);
} else {
r.push(if f.len() % 2 == 0 { 1 } else { -1 });
}
}
r
}
fn modpow_128bit(mut s: u128, mut n: u128, p: u128) -> u128 {
if p == 0 {
return 1;
}
let mut t = s;
s = 1;
while n > 0 {
if n & 1 != 0 {
s *= t;
s %= p;
}
n >>= 1;
t *= t;
t %= p;
}
s
}
fn modpow_64bit(mut s: u64, mut n: u64, p: u64) -> u64 {
if p == 0 {
return 1;
}
let mut t = s;
s = 1;
while n > 0 {
if n & 1 != 0 {
s *= t;
s %= p;
}
n >>= 1;
t *= t;
t %= p;
}
s
}
pub fn miller_rabin(n: u64) -> bool {
if n == 2 {
return true;
}
if n == 1 || n % 2 == 0 {
return false;
}
let (mut s, mut t) = (0, n - 1);
while t % 2 == 0 {
s += 1;
t >>= 1;
}
let arr = if n < 4_759_123_141 {
vec![2, 7, 61]
} else if n < 341_550_071_728_321 {
vec![2, 3, 5, 7, 11, 13, 17]
} else if n < 3_825_123_056_546_413_051 {
vec![2, 3, 5, 7, 11, 13, 17, 19, 23]
} else {
vec![2, 325, 9_375, 28_178, 450_775, 9_780_504, 1_795_265_022]
}
.iter()
.filter(|&&q| q < n)
.cloned()
.collect::<Vec<_>>();
let millor_rabin_inner = |a| {
if modpow_128bit(a as u128, t as u128, n as u128) == 1 {
return true;
}
for i in 0..s {
if modpow_128bit(a as u128, 2_u128.pow(i) * t as u128, n as u128) as u64 == n - 1 {
return true;
}
}
false
};
let millor_rabin_inner_small = |a| {
if modpow_64bit(a, t, n) == 1 {
return true;
}
for i in 0..s {
if modpow_64bit(a, 2_u64.pow(i) * t, n) == n - 1 {
return true;
}
}
false
};
if n < 1_000_000_000 {
for a in arr {
if !millor_rabin_inner_small(a) {
return false;
}
}
} else {
for a in arr {
if !millor_rabin_inner(a) {
return false;
}
}
}
true
}
fn gcd_u64(a: u64, b: u64) -> u64
where
{
if b + b == b {
return a;
}
gcd_u64(b, a % b)
}
pub struct PollardRho {
arr: Vec<u64>,
}
impl PollardRho {
pub fn calc(n: u64) -> PollardRho {
PollardRho { arr: vec![n] }
}
}
impl Iterator for PollardRho {
type Item = ValueType;
#[allow(clippy::many_single_char_names)]
fn next(&mut self) -> Option<Self::Item> {
if self.arr.is_empty() || self.arr[0] == 0 {
return None;
}
let n = self.arr.pop().unwrap();
if n == 1 {
return None;
}
if miller_rabin(n) {
let r = n;
return Some(r);
}
if n % 2 == 0 {
self.arr.push(n / 2);
return Some(2);
}
let f = |x, seed| ((x as u128 * x as u128 + seed as u128) % n as u128) as u64;
let f_small = |x, seed| ((x * x + seed) % n);
for s in 1.. {
let (mut x, mut y, mut d) = (2, 2, 1);
while d == 1 {
if n <= 1_000_000_000 {
x = f_small(x, s);
y = f_small(f_small(y, s), s);
} else {
x = f(x, s);
y = f(f(y, s), s);
}
d = gcd_u64(std::cmp::max(x, y) - std::cmp::min(x, y), n)
}
if d != n {
self.arr.push(n / d);
self.arr.push(d);
return self.next();
}
}
panic![]
}
}
}
pub mod twosat {
use crate::internal_scc;
pub struct TwoSat {
n: usize,
scc: internal_scc::SccGraph,
answer: Vec<bool>,
}
impl TwoSat {
pub fn new(n: usize) -> Self {
TwoSat {
n,
answer: vec![false; n],
scc: internal_scc::SccGraph::new(2 * n),
}
}
pub fn add_clause(&mut self, i: usize, f: bool, j: usize, g: bool) {
assert!(i < self.n && j < self.n);
self.scc.add_edge(2 * i + !f as usize, 2 * j + g as usize);
self.scc.add_edge(2 * j + !g as usize, 2 * i + f as usize);
}
pub fn satisfiable(&mut self) -> bool {
let id = self.scc.scc_ids().1;
for i in 0..self.n {
if id[2 * i] == id[2 * i + 1] {
return false;
}
self.answer[i] = id[2 * i] < id[2 * i + 1];
}
true
}
pub fn answer(&self) -> &[bool] {
&self.answer
}
}
}