結果

問題 No.1955 Not Prime
ユーザー miyo2580miyo2580
提出日時 2024-02-13 23:08:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 6,603 bytes
コンパイル時間 3,244 ms
コンパイル使用メモリ 229,344 KB
実行使用メモリ 19,596 KB
最終ジャッジ日時 2024-02-13 23:08:12
合計ジャッジ時間 5,827 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
7,708 KB
testcase_01 AC 12 ms
7,708 KB
testcase_02 AC 11 ms
7,708 KB
testcase_03 AC 12 ms
7,708 KB
testcase_04 AC 11 ms
7,708 KB
testcase_05 AC 12 ms
7,708 KB
testcase_06 AC 12 ms
7,816 KB
testcase_07 AC 26 ms
8,896 KB
testcase_08 AC 22 ms
8,692 KB
testcase_09 AC 33 ms
8,696 KB
testcase_10 AC 24 ms
7,708 KB
testcase_11 AC 38 ms
19,596 KB
testcase_12 AC 17 ms
8,200 KB
testcase_13 AC 34 ms
8,896 KB
testcase_14 AC 15 ms
8,328 KB
testcase_15 AC 14 ms
8,200 KB
testcase_16 AC 19 ms
8,692 KB
testcase_17 AC 27 ms
10,048 KB
testcase_18 AC 33 ms
8,896 KB
testcase_19 AC 31 ms
9,792 KB
testcase_20 AC 11 ms
7,708 KB
testcase_21 AC 17 ms
8,200 KB
testcase_22 AC 11 ms
7,708 KB
testcase_23 AC 11 ms
7,708 KB
testcase_24 AC 11 ms
7,708 KB
testcase_25 AC 11 ms
7,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

//https://nyaannyaan.github.io/library/math/two-sat.hpp.html

namespace TwoSatImpl {
namespace internal {

template <class E>
struct csr {
  vector<int> start;
  vector<E> elist;
  csr(int n, const vector<pair<int, E>>& edges)
      : start(n + 1), elist(edges.size()) {
    for (auto e : edges) {
      start[e.first + 1]++;
    }
    for (int i = 1; i <= n; i++) {
      start[i] += start[i - 1];
    }
    auto counter = start;
    for (auto e : edges) {
      elist[counter[e.first]++] = e.second;
    }
  }
};

struct scc_graph {
 public:
  scc_graph(int n) : _n(n) {}

  int num_vertices() { return _n; }

  void add_edge(int from, int to) { edges.push_back({from, {to}}); }

  pair<int, vector<int>> scc_ids() {
    auto g = csr<edge>(_n, edges);
    int now_ord = 0, group_num = 0;
    vector<int> visited, low(_n), ord(_n, -1), ids(_n);
    visited.reserve(_n);
    auto dfs = [&](auto self, int v) -> void {
      low[v] = ord[v] = now_ord++;
      visited.push_back(v);
      for (int i = g.start[v]; i < g.start[v + 1]; i++) {
        auto to = g.elist[i].to;
        if (ord[to] == -1) {
          self(self, to);
          low[v] = min(low[v], low[to]);
        } else {
          low[v] = min(low[v], ord[to]);
        }
      }
      if (low[v] == ord[v]) {
        while (true) {
          int u = visited.back();
          visited.pop_back();
          ord[u] = _n;
          ids[u] = group_num;
          if (u == v) break;
        }
        group_num++;
      }
    };
    for (int i = 0; i < _n; i++) {
      if (ord[i] == -1) dfs(dfs, i);
    }
    for (auto& x : ids) {
      x = group_num - 1 - x;
    }
    return {group_num, ids};
  }

  vector<vector<int>> scc() {
    auto ids = scc_ids();
    int group_num = ids.first;
    vector<int> counts(group_num);
    for (auto x : ids.second) counts[x]++;
    vector<vector<int>> groups(ids.first);
    for (int i = 0; i < group_num; i++) {
      groups[i].reserve(counts[i]);
    }
    for (int i = 0; i < _n; i++) {
      groups[ids.second[i]].push_back(i);
    }
    return groups;
  }

  void add_node_size(int m) { _n += m; }
  int size() { return _n; }

 private:
  int _n;
  struct edge {
    int to;
  };
  vector<pair<int, edge>> edges;
};

}  // namespace internal

struct two_sat {
 public:
  two_sat() : _n(0), built(false), scc(0) {}
  two_sat(int n) : _n(n), built(false), scc(2 * n) {}

  int add_var() {
    scc.add_node_size(2);
    return _n++;
  }

  // (not i) は ~i で渡す
  void add_clause(int i, int j) {
    i = max(2 * i, -1 - 2 * i);
    j = max(2 * j, -1 - 2 * j);
    assert(0 <= i && i < 2 * _n);
    assert(0 <= j && j < 2 * _n);
    scc.add_edge(i, j ^ 1);
    scc.add_edge(j, i ^ 1);
  }
  void if_then(int i, int j) { add_clause(~i, j); }
  void set_val(int i) { add_clause(i, i); }

  // (not i) は ~i で渡す
  void at_most_one(const vector<int>& nodes) {
    if ((int)nodes.size() <= 1) return;
    int cur = ~nodes[0];
    for (int i = 2; i < (int)nodes.size(); i++) {
      int nxt = add_var(), n_i = ~nodes[i];
      add_clause(cur, n_i);
      add_clause(cur, nxt);
      add_clause(n_i, nxt);
      cur = ~nxt;
    }
    add_clause(cur, ~nodes[1]);
  }

  bool satisfiable() {
    _answer.resize(_n);
    built = true;
    auto id = scc.scc_ids().second;
    for (int i = 0; i < _n; i++) {
      if (id[2 * i] == id[2 * i + 1]) {
        _answer.clear();
        return false;
      }
      _answer[i] = id[2 * i] < id[2 * i + 1];
    }
    return true;
  }
  vector<bool> answer() {
    if (!built) satisfiable();
    return _answer;
  }

 private:
  int _n;
  vector<bool> _answer;
  bool built;
  internal::scc_graph scc;
};

}  // namespace TwoSatImpl

using TwoSatImpl::two_sat;

// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factor(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
}sieve(999999);

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    vec a(n),b(n);
    rep(i,n){
      cin>>a[i]>>b[i];
    }
    auto f=[&](ll x,ll y){
      int res=0;
      ll now=1;
      while(y){
        res+=now*(y%10);
        y/=10;
        now*=10;
      }
      while(x){
        res+=now*(x%10);
        x/=10;
        now*=10;
      }
      return res;
    };
    bool ans=1;
    two_sat ts(n);
    rep(i,n)repd(j,i,n){
      if(i==j){
        ll cnt=0;
        if(sieve.isPrime(f(a[i],b[i]))){
          cnt++;
          ts.set_val(~i);
        }
        if(sieve.isPrime(f(b[i],a[i]))){
          cnt++;
          ts.set_val(i);
        }
        if(cnt==2)ans=0;
        continue;
      }
      if(sieve.isPrime(f(a[i],a[j]))||sieve.isPrime(f(b[j],b[i]))){
        ts.add_clause(~i,j);
      }
      if(sieve.isPrime(f(a[i],b[j]))||sieve.isPrime(f(a[j],b[i]))){
        ts.add_clause(~i,~j);
      }
      if(sieve.isPrime(f(b[i],a[j]))||sieve.isPrime(f(b[j],a[i]))){
        ts.add_clause(i,j);
      }
      if(sieve.isPrime(f(b[i],b[j]))||sieve.isPrime(f(a[j],a[i]))){
        ts.add_clause(i,~j);
      }
    }
    if(!ts.satisfiable())ans=0;
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
0