#1142168 (Rust) No.5005 3-SAT

• 問題: No.5005 3-SAT
• ユーザー: Tekyla
• 提出日時: 2025-12-29 15:21:19
• 言語: Rust (1.92.0 + proconio + num)
• 結果: AC
• 実行時間: 1,952 ms / 2,000 ms
• コード長: 2,931 bytes
• コンパイル時間: 12,519 ms
• コンパイル使用メモリ: 400,256 KB
• 実行使用メモリ: 7,848 KB
• スコア: 831
• 最終ジャッジ日時: 2025-12-29 15:24:54
• 合計ジャッジ時間: 213,086 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

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

コンパイルメッセージ

warning: unexpected `cfg` condition value: `local`
  --> src/main.rs:20:15
   |
20 |         #[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:24:19
   |
24 |         #[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

warning: method `next_bool_u8` is never used
  --> src/main.rs:52:8
   |
37 | impl XorShift32 {
   | --------------- method in this implementation
...
52 |     fn next_bool_u8(&mut self) -> u8 {
   |        ^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `generate_arr` is never used
  --> src/main.rs:58:4
   |
58 | fn generate_arr(rng: &mut XorShift32) -> [u8; 256] {
   |    ^^^^^^^^^^^^

warning: method `isTimeOver` should have a snake case name
  --> src/main.rs:18:8
   |
18 |     fn isTimeOver(&self) -> bool {
   |        ^^^^^^^^^^ help: convert the identifier to snake case: `is_time_over`
   |
   = note: `#[warn(non_snake_case)]` on by default

ソースコード

use proconio::input;

const N: usize = 2048;

// 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]
    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
        }
    }
}

// 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 }
    }
    // 次の乱数を生成
    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; 256] {
    let mut res = [0_u8; 256];
    for i in 0..256 {
        res[i] = rng.next_bool_u8();
    }
    res
}

// 後ろの制約から決めていく
fn generate_arr2(
    rng: &mut XorShift32,
    constraint: &Vec<(usize, usize, usize, u8, u8, u8)>,
) -> [u8; 256] {
    let mut res = [0_u8; 256];
    for i in (0..N).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; 256], constraint: &Vec<(usize, usize, usize, u8, u8, u8)>) -> u32 {
    for i in 0..N {
        let &(a, b, c, p, q, r) = &constraint[i];
        if (arr[a] != p) & (arr[b] != q) & (arr[c] != r) {
            return i as u32;
        }
    }
    N as u32
}

fn main() {
    // タイマー
    let timer = TimeKeeper::new(1.95);
    // 入力
    input! {
        constraint:[(usize, usize, usize, u8,u8,u8);N]
    }

    // 時間いっぱいランダムに回す
    let mut rng = XorShift32::new(4869);
    let mut best_arr = generate_arr2(&mut rng, &constraint);
    let mut best_score = calc_score(&best_arr, &constraint);

    while !timer.isTimeOver() {
        let arr = generate_arr2(&mut rng, &constraint);
        let score = calc_score(&arr, &constraint);
        if best_score < score {
            best_score = score;
            best_arr = arr;
        }
    }
    // 出力
    for a in best_arr {
        print!("{a}")
    }
}