結果

問題 No.1955 Not Prime
コンテスト
ユーザー tttmmmyyyy
提出日時 2026-10-28 09:02:09
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 59 ms / 2,000 ms
+ 78µs
コード長 1,825 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,629 ms
コンパイル使用メモリ 684,648 KB
実行使用メモリ 32,672 KB
最終ジャッジ日時 2026-10-28 09:02:27
合計ジャッジ時間 14,958 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.UnionFind;
import CPLib.TwoSat;

// ps : Array U32 = calc_prime_list(1e6);

pt : BoolArray = calc_prime_table(1e6);

hate : I64 -> I64 -> Bool = |a, b| (
    let x = (a.to_string + b.to_string).from_string.as_ok : I64;
    pt.@(x)
);

main : IO () = (
    let n = *read_i;
    let (as, bs) = *range(0, n).fold_m(([], []), |_, (as, bs)|
        let a = *read_i;
        let b = *read_i;
        (as.push_back(a), bs.push_back(b)).pure
    );
    let ts = TwoSat::create(n);

    // Ai hates Bi => not pi
    // Ai hates Bj => not pi or not pj
    let ts = range(0, n).fold(ts, |i, ts|
        range(0, n).fold(ts, |j, ts|
            if !hate(as.@(i), bs.@(j)) { ts };
            if i == j { ts.add_clause(i, false, i, false) };
            ts.add_clause(i, false, j, false)
        )
    );

    // Bi hates Ai => pi 
    // Bj hates Ai => pi or pj
    let ts = range(0, n).fold(ts, |i, ts|
        range(0, n).fold(ts, |j, ts|
            if !hate(bs.@(j), as.@(i)) { ts };
            if i == j { ts.add_clause(i, true, i, true) };
            ts.add_clause(i, true, j, true)
        )
    );

    // Ai hate Aj => not pi or pj
    let ts = range(0, n).fold(ts, |i, ts|
        range(0, n).fold(ts, |j, ts|
            if i == j || !hate(as.@(i), as.@(j)) { ts };
            ts.add_clause(i, false, j, true)
        )
    );

    // Bi hate Bj => pi or not pj
    let ts = range(0, n).fold(ts, |i, ts|
        range(0, n).fold(ts, |j, ts|
            if i == j || !hate(bs.@(i), bs.@(j)) { ts };
            ts.add_clause(i, true, j, false)
        )
    );    

    let ok = ts.solve;

    if ok.is_some {
        println("Yes")    
    } else {
        println("No")
    };;

    pure()
);
0