結果
| 問題 | No.5005 3-SAT |
| ユーザー |
 Tekyla
|
| 提出日時 | 2025-12-30 19:43:19 |
| 言語 | Rust (1.92.0 + proconio + num) |
| 結果 |
AC
|
| 実行時間 | 1,971 ms / 2,000 ms |
| コード長 | 22,407 bytes |
| 記録 | |
| コンパイル時間 | 14,236 ms |
| コンパイル使用メモリ | 397,940 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 84,519 |
| 最終ジャッジ日時 | 2025-12-30 19:46:55 |
| 合計ジャッジ時間 | 215,480 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:264:15
|
264 | #[cfg(feature = "local")]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
= note: `#[warn(unexpected_cfgs)]` on by default
warning: unexpected `cfg` condition value: `local`
--> src/main.rs:268:19
|
268 | #[cfg(not(feature = "local"))]
| ^^^^^^^^^^^^^^^^^ help: remove the condition
|
= note: no expected values for `feature`
= help: consider adding `local` as a feature in `Cargo.toml`
= note: see <https://doc.rust-lang.org/nightly/rustc/check-cfg/cargo-specifics.html> for more information about checking conditional configuration
ソースコード
#![allow(unused)]
use proconio::input;
// N:文字列の長さ, M:節の数
const N: usize = 256;
//const N: usize = 24;
const M: usize = 2048;
// two sat を librarycheckerから引っ張ってくる
pub mod jagged {
use std::fmt::Debug;
use std::mem::MaybeUninit;
use std::ops::{Index, IndexMut};
// Compressed sparse row format, for static jagged array
// Provides good locality for graph traversal
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct CSR<T> {
pub links: Vec<T>,
head: Vec<u32>,
}
impl<T: Clone> CSR<T> {
pub fn from_pairs(n: usize, pairs: impl Iterator<Item = (u32, T)> + Clone) -> Self {
let mut head = vec![0u32; n + 1];
for (u, _) in pairs.clone() {
debug_assert!(u < n as u32);
head[u as usize] += 1;
}
for i in 0..n {
head[i + 1] += head[i];
}
let mut data: Vec<_> = (0..head[n]).map(|_| MaybeUninit::uninit()).collect();
for (u, v) in pairs {
head[u as usize] -= 1;
data[head[u as usize] as usize] = MaybeUninit::new(v.clone());
}
// Rustc is likely to perform in‑place iteration without new allocation.
// [https://doc.rust-lang.org/stable/std/iter/trait.FromIterator.html#impl-FromIterator%3CT%3E-for-Vec%3CT%3E]
let data = data
.into_iter()
.map(|x| unsafe { x.assume_init() })
.collect();
CSR { links: data, head }
}
}
impl<T, I> FromIterator<I> for CSR<T>
where
I: IntoIterator<Item = T>,
{
fn from_iter<J>(iter: J) -> Self
where
J: IntoIterator<Item = I>,
{
let mut data = vec![];
let mut head = vec![];
head.push(0);
let mut cnt = 0;
for row in iter {
data.extend(row.into_iter().inspect(|_| cnt += 1));
head.push(cnt);
}
CSR { links: data, head }
}
}
impl<T> CSR<T> {
pub fn len(&self) -> usize {
self.head.len() - 1
}
pub fn edge_range(&self, index: usize) -> std::ops::Range<usize> {
self.head[index] as usize..self.head[index as usize + 1] as usize
}
}
impl<T> Index<usize> for CSR<T> {
type Output = [T];
fn index(&self, index: usize) -> &Self::Output {
&self.links[self.edge_range(index)]
}
}
impl<T> IndexMut<usize> for CSR<T> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
let es = self.edge_range(index);
&mut self.links[es]
}
}
impl<T> Debug for CSR<T>
where
T: Debug,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let v: Vec<Vec<&T>> = (0..self.len()).map(|i| self[i].iter().collect()).collect();
v.fmt(f)
}
}
}
fn gen_scc(children: &jagged::CSR<u32>) -> (usize, Vec<u32>) {
// Tarjan algorithm, iterative
let n = children.len();
const UNSET: u32 = !0;
let mut scc_index = vec![UNSET; n];
let mut n_scc = 0;
// Stackless DFS
let mut parent = vec![UNSET; n];
let mut current_edge: Vec<_> = (0..n)
.map(|u| children.edge_range(u).start as u32)
.collect();
let mut t_in = vec![0u32; n];
let mut timer = 1;
let mut low_link = vec![UNSET; n];
let mut path_stack = vec![];
for mut u in 0..n as u32 {
if t_in[u as usize] > 0 {
continue;
}
parent[u as usize] = u;
loop {
let e = current_edge[u as usize];
current_edge[u as usize] += 1;
if e == children.edge_range(u as usize).start as u32 {
// On enter
t_in[u as usize] = timer;
low_link[u as usize] = timer;
timer += 1;
path_stack.push(u);
}
if e < children.edge_range(u as usize).end as u32 {
let v = children.links[e as usize];
if t_in[v as usize] == 0 {
// Front edge
parent[v as usize] = u;
u = v;
} else if scc_index[v as usize] == UNSET {
// Back edge or cross edge, scc not constructed yet
low_link[u as usize] = low_link[u as usize].min(t_in[v as usize]);
}
} else {
// On exit
if low_link[u as usize] == t_in[u as usize] {
// Found a scc
loop {
let v = path_stack.pop().unwrap();
scc_index[v as usize] = n_scc;
if v == u {
break;
}
}
n_scc += 1;
}
let p = parent[u as usize];
if p == u {
break;
}
low_link[p as usize] = low_link[p as usize].min(low_link[u as usize]);
u = p;
}
}
}
(n_scc as usize, scc_index)
}
pub struct TwoSat {
n_props: usize,
edges: Vec<(u32, u32)>,
}
impl TwoSat {
pub fn new(n_props: usize) -> Self {
Self {
n_props,
edges: vec![],
}
}
pub fn add_disj(&mut self, (p, bp): (u32, bool), (q, bq): (u32, bool)) {
self.edges
.push((self.prop_to_node((p, !bp)), self.prop_to_node((q, bq))));
self.edges
.push((self.prop_to_node((q, !bq)), self.prop_to_node((p, bp))));
}
fn prop_to_node(&self, (p, bp): (u32, bool)) -> u32 {
debug_assert!(p < self.n_props as u32);
if bp { p } else { self.n_props as u32 + p }
}
fn node_to_prop(&self, node: u32) -> (u32, bool) {
if node < self.n_props as u32 {
(node, true)
} else {
(node - self.n_props as u32, false)
}
}
pub fn solve(&self) -> Option<Vec<bool>> {
let children = jagged::CSR::from_pairs(self.n_props * 2, self.edges.iter().copied());
let (n_scc, scc_index) = gen_scc(&children);
let scc = jagged::CSR::from_pairs(
n_scc,
(0..self.n_props * 2).map(|u| (scc_index[u], u as u32)),
);
for p in 0..self.n_props as u32 {
if scc_index[self.prop_to_node((p, true)) as usize]
== scc_index[self.prop_to_node((p, false)) as usize]
{
return None;
}
}
let mut interpretation = vec![2u8; self.n_props];
for u in 0..n_scc {
for &i in &scc[u] {
let (p, v) = self.node_to_prop(i);
if interpretation[p as usize] != 2u8 {
break;
}
interpretation[p as usize] = v as u8;
}
}
Some(interpretation.into_iter().map(|x| x != 0).collect())
}
}
// https://zenn.dev/tipstar0125/articles/245bceec86e40a
struct TimeKeeper {
t_start: std::time::Instant,
t_threshold: f64,
}
impl TimeKeeper {
fn new(t_threshold: f64) -> Self {
TimeKeeper {
t_start: std::time::Instant::now(),
t_threshold,
}
}
#[inline]
#[allow(non_snake_case)]
fn isTimeOver(&self) -> bool {
let elapsed_time = self.t_start.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 0.85 >= self.t_threshold
}
#[cfg(not(feature = "local"))]
{
elapsed_time >= self.t_threshold
}
}
fn get_elapsed_time(&self) -> f64 {
self.t_start.elapsed().as_nanos() as f64 * 1e-9
}
}
// XorShift
// https://gemini.google.com/app/3ddaf2f301e50794?utm_source=app_launcher&utm_medium=owned&utm_campaign=base_all
struct XorShift32 {
state: u32,
}
impl XorShift32 {
// 初期シード
fn new(seed: u32) -> Self {
XorShift32 { state: seed }
}
// 関数を呼び出すコードを、その関数の中身（本体）で直接置き換える
// 小さい処理を大量に呼び出す場合につけるとよい
#[inline]
// 次の乱数を生成
fn next_u32(&mut self) -> u32 {
let mut x = self.state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
self.state = x;
x
}
//
fn next_bool_u8(&mut self) -> u8 {
(self.next_u32() & 1) as u8
}
}
// ランダムに0,1 を256個出力する
fn generate_arr(rng: &mut XorShift32) -> [u8; N] {
let mut res = [0_u8; N];
for i in 0..N {
res[i] = rng.next_bool_u8();
}
res
}
// 後ろの制約から決めていく
fn generate_arr2(
rng: &mut XorShift32,
constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
) -> [u8; N] {
let mut res = [0_u8; N];
for i in (0..M).rev() {
let &(a, b, c, p, q, r) = &constraint[i];
let random = rng.next_u32();
match random % 3 {
0 => res[a] = p,
1 => res[b] = q,
2 => res[c] = r,
_ => unreachable!(),
}
}
res
}
// スコア計算
fn calc_score(arr: &[u8; N], constraint: &Vec<(usize, usize, usize, u8, u8, u8)>) -> u32 {
for i in 0..M {
let &(a, b, c, p, q, r) = &constraint[i];
if (arr[a] != p) & (arr[b] != q) & (arr[c] != r) {
return i as u32;
}
}
M as u32
}
// solver_dfc
// 普通に深さ優先探索するとどうなる？
fn dfs(
arr: &mut [u8; N],
constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
i: usize,
rng: &mut XorShift32,
timer: &TimeKeeper,
) -> (u32, [u8; N]) {
let mut best_score: u32 = i as u32;
let mut best_arr: [u8; N] = *arr;
if timer.isTimeOver() || (i >= M) {
return (best_score, best_arr);
}
let &(a, b, c, p, q, r) = &constraint[i];
// すでに条件達成済み
if (arr[a] == p) || (arr[b] == q) || (arr[c] == r) {
return dfs(arr, &constraint, i + 1, rng, &timer);
} else {
// ここから条件を動かす
if arr[a] == 2 {
arr[a] = p;
let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
if score_tmp > best_score {
best_score = score_tmp;
best_arr = arr_tmp;
}
arr[a] = 2;
}
if arr[b] == 2 {
if timer.isTimeOver() {
return (best_score, best_arr);
}
arr[b] = q;
let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
if score_tmp > best_score {
best_score = score_tmp;
best_arr = arr_tmp;
}
arr[b] = 2;
}
if arr[c] == 2 {
if timer.isTimeOver() {
return (best_score, best_arr);
}
arr[c] = r;
let (score_tmp, arr_tmp) = dfs(arr, constraint, i + 1, rng, timer);
if score_tmp > best_score {
best_score = score_tmp;
best_arr = arr_tmp;
}
arr[c] = 2;
}
return (best_score, best_arr);
}
}
// solver(two-satベース)
fn solver_twosat(
constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
rng: &mut XorShift32,
timer: &TimeKeeper,
) -> (u32, [u8; N]) {
// 制約0(0 or 1), 1(0 or 2), 2(1 or 2)
let mut cnf_list = [0_u8; M];
for i in 0..M {
cnf_list[i] = (rng.next_u32() % 3) as u8;
}
// 初期cnf_listでokの範囲をにぶたん
let mut ok = 0_usize;
let mut ng = M;
let mut result: Vec<bool> = vec![];
while ng - ok > 1 {
let mid = (ok + ng) / 2;
let mut two_sat = TwoSat::new(N);
for i in 0..=mid {
let &(a, b, c, p, q, r) = &constraint[i];
match cnf_list[i] {
0 => two_sat.add_disj((a as u32, p == 0), (b as u32, q == 0)),
1 => two_sat.add_disj((a as u32, p == 0), (c as u32, r == 0)),
2 => two_sat.add_disj((b as u32, q == 0), (c as u32, r == 0)),
_ => unreachable!(),
}
}
if let Some(result_binary_search) = two_sat.solve() {
ok = mid;
result = result_binary_search;
} else {
ng = mid;
}
}
// ここから時間いっぱい頑張る
while !timer.isTimeOver() {
// cnf_list の更新
for i in 0..=(ok + 2).min(M - 1) {
let &(a, b, c, p, q, r) = &constraint[i];
let cnf_rng = (rng.next_u32() % 3) as u8;
let mut change_flag = false;
if cnf_rng == 0 {
if (result[a] == (p == 0)) || (result[b] == (q == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else if cnf_rng == 1 {
if (result[a] == (p == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else {
if (result[b] == (q == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
}
// cnf_+1を回す
if change_flag {
continue;
}
let cnf_rng = (cnf_rng + 1) % 3;
if cnf_rng == 0 {
if (result[a] == (p == 0)) || (result[b] == (q == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else if cnf_rng == 1 {
if (result[a] == (p == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else {
if (result[b] == (q == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
}
}
// two_satを解く
for ok_i in (ok + 1)..M {
let mut two_sat = TwoSat::new(N);
for i in 0..=ok_i {
let &(a, b, c, p, q, r) = &constraint[i];
match cnf_list[i] {
0 => two_sat.add_disj((a as u32, p == 0), (b as u32, q == 0)),
1 => two_sat.add_disj((a as u32, p == 0), (c as u32, r == 0)),
2 => two_sat.add_disj((b as u32, q == 0), (c as u32, r == 0)),
_ => unreachable!(),
}
}
if let Some(result_tmp) = two_sat.solve() {
result = result_tmp;
ok = ok_i;
} else {
break;
}
}
}
let mut ans = [0; N];
for i in 0..N {
if !result[i] {
ans[i] = 1_u8;
}
}
return (ok as u32, ans);
}
fn create_init_cnf_list(constraint: &Vec<(usize, usize, usize, u8, u8, u8)>, limit:usize) -> [u8;M]{
// 全部は無謀なので、limit までをなるべく満たすようなcnfを探してみる
let mut counter = [0; N];
for i in 0..limit.min(M){
let &(a,b,c,p,q,r) = &constraint[i];
counter[a] += (p as i32)*2 - 1;
counter[b] += (q as i32)*2 - 1;
counter[c] += (r as i32)*2 - 1;
}
// なるべく候補が多いやつを選ぶ
let mut cnf_list = [0_u8; M];
for i in 0..limit.min(M) {
let &(a,b,c,p,q,r) = &constraint[i];
let ai = counter[a] * (2*p as i32-1);
let bi = counter[b] * (2*q as i32-1);
let ci = counter[c] * (2*r as i32-1);
if ai >= bi {
if bi >= ci{
continue;
}else{
cnf_list[i] = 1_u8;
}
}else{
if ai >= ci{
continue;
}else{
cnf_list[i] = 2_u8;
}
}
}
return cnf_list;
}
// solver2(two-satベース)
fn solver2_twosat(
constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
rng: &mut XorShift32,
timer: &TimeKeeper,
) -> (u32, [u8; N]) {
// 1秒間ランダムに、そのあとは頑張る
// 制約0(0 or 1), 1(0 or 2), 2(1 or 2)
let mut cnf_list = create_init_cnf_list(&constraint, 1000);
// 初期cnf_listでokの範囲をにぶたん
let mut ok = 0_usize;
let mut ng = M;
let mut result: Vec<bool> = vec![];
while ng - ok > 1 {
let mid = (ok + ng) / 2;
let mut two_sat = TwoSat::new(N);
for i in 0..=mid {
let &(a, b, c, p, q, r) = &constraint[i];
match cnf_list[i] {
0 => two_sat.add_disj((a as u32, p == 0), (b as u32, q == 0)),
1 => two_sat.add_disj((a as u32, p == 0), (c as u32, r == 0)),
2 => two_sat.add_disj((b as u32, q == 0), (c as u32, r == 0)),
_ => unreachable!(),
}
}
if let Some(result_binary_search) = two_sat.solve() {
ok = mid;
result = result_binary_search;
} else {
ng = mid;
}
}
// ここから時間いっぱい頑張る,1秒間はただランダムに、あとは1節ずつ広げていくように
while !timer.isTimeOver() {
// cnf_list の更新
for i in 0..=(ok + 2).min(M - 1) {
let &(a, b, c, p, q, r) = &constraint[i];
let cnf_rng = (rng.next_u32() % 3) as u8;
let mut change_flag = false;
if cnf_rng == 0 {
if (result[a] == (p == 0)) || (result[b] == (q == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else if cnf_rng == 1 {
if (result[a] == (p == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else {
if (result[b] == (q == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
}
// cnf_+1を回す
if change_flag {
continue;
}
let cnf_rng = (cnf_rng + 1) % 3;
if cnf_rng == 0 {
if (result[a] == (p == 0)) || (result[b] == (q == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else if cnf_rng == 1 {
if (result[a] == (p == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
} else {
if (result[b] == (q == 0)) || (result[c] == (r == 0)) {
cnf_list[i] = cnf_rng;
change_flag = true;
}
}
}
// two_satを解く
for ok_i in (ok + 1)..M {
let mut two_sat = TwoSat::new(N);
for i in 0..=ok_i {
let &(a, b, c, p, q, r) = &constraint[i];
match cnf_list[i] {
0 => two_sat.add_disj((a as u32, p == 0), (b as u32, q == 0)),
1 => two_sat.add_disj((a as u32, p == 0), (c as u32, r == 0)),
2 => two_sat.add_disj((b as u32, q == 0), (c as u32, r == 0)),
_ => unreachable!(),
}
}
if let Some(result_tmp) = two_sat.solve() {
result = result_tmp;
ok = ok_i;
//println!("{}[s], {}", timer.get_elapsed_time(), ok);
} else {
break;
}
}
if ok == M - 1 {
break;
}
//1秒経過した場合、次のようなcnfを試す
if timer.get_elapsed_time() > 1.0 {
let mut cnf_list_copy = cnf_list.clone();
let &(a, b, c, p, q, r) = &constraint[ok + 1];
// なるべく成立させる条件を選ぶ
let (abc, pqr) = match rng.next_u32() % 3 {
0 => (a, p),
1 => (b, q),
_ => (c, r),
};
// 条件を調整する
for i in 0..=ok {
let &(aa, bb, cc, pp, qq, rr) = &constraint[i];
if (aa == abc) && (pp != pqr) {
cnf_list_copy[i] = 2;
} else if (bb == abc) && (qq != pqr) {
cnf_list_copy[i] = 1;
} else if (cc == abc) && (rr != pqr) {
cnf_list_copy[i] = 0;
}
}
// two_satを解いてみる
let mut two_sat = TwoSat::new(N);
for i in 0..=(ok+1) {
let &(a, b, c, p, q, r) = &constraint[i];
match cnf_list_copy[i] {
0 => two_sat.add_disj((a as u32, p == 0), (b as u32, q == 0)),
1 => two_sat.add_disj((a as u32, p == 0), (c as u32, r == 0)),
2 => two_sat.add_disj((b as u32, q == 0), (c as u32, r == 0)),
_ => unreachable!(),
}
}
if let Some(result_tmp) = two_sat.solve() {
result = result_tmp;
ok += 1;
cnf_list = cnf_list_copy;
//println!("{}[s], {}, 新しいやつ", timer.get_elapsed_time(), ok);
}
}
}
let mut ans = [0; N];
for i in 0..N {
if !result[i] {
ans[i] = 1_u8;
}
}
return (ok as u32, ans);
}
fn main() {
// タイマー
let timer = TimeKeeper::new(1.95);
// 入力
input! {
constraint:[(usize, usize, usize, u8,u8,u8);M]
}
// 乱数初期化
let mut rng = XorShift32::new(4869);
let (best_score, best_arr) = solver2_twosat(&constraint, &mut rng, &timer);
// 出力
//eprintln!("{best_score}");
for &a in best_arr.iter().rev() {
if a == 2 { print!("0") } else { print!("{a}") }
}
}