結果
問題 |
No.1955 Not Prime
|
ユーザー |
|
提出日時 | 2022-05-20 22:07:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 1,590 bytes |
コンパイル時間 | 2,419 ms |
コンパイル使用メモリ | 216,048 KB |
最終ジャッジ日時 | 2025-01-29 10:41:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _RUTHEN #include "debug.hpp" #else #define show(...) true #endif vector<bool> Era(int n) { vector<bool> isprime(n + 1, 1); isprime[0] = 0; isprime[1] = 0; for (int i = 2; i < n + 1; i++) { if (isprime[i]) { for (int j = 2 * i; j < n + 1; j += i) isprime[j] = 0; } } return isprime; } #include <atcoder/twosat> using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) template <class T> using V = vector<T>; int main() { ios::sync_with_stdio(false); cin.tie(0); auto era = Era(1000000); int N; cin >> N; V<string> A(N), B(N); rep(i, N) cin >> A[i] >> B[i]; atcoder::two_sat ts(2 * N); rep(i, N) ts.add_clause(i, true, i + N, true); rep(i, N) ts.add_clause(i, false, i + N, false); rep(i, N) { rep(j, N) { if (era[stoi(A[i] + A[j])]) ts.add_clause(i, false, j, true); if (era[stoi(A[i] + B[j])]) ts.add_clause(i, false, j + N, true); if (era[stoi(B[i] + A[j])]) ts.add_clause(i + N, false, j, true); if (era[stoi(B[i] + B[j])]) ts.add_clause(i + N, false, j + N, true); if (era[stoi(A[j] + A[i])]) ts.add_clause(j, false, i, true); if (era[stoi(A[j] + B[i])]) ts.add_clause(j, false, i + N, true); if (era[stoi(B[j] + A[i])]) ts.add_clause(j + N, false, i, true); if (era[stoi(B[j] + B[i])]) ts.add_clause(j + N, false, i + N, true); } } cout << (ts.satisfiable() ? "Yes" : "No") << '\n'; return 0; }