結果

問題 No.1955 Not Prime
ユーザー eQeeQe
提出日時 2022-05-28 11:16:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 5,150 bytes
コンパイル時間 5,080 ms
コンパイル使用メモリ 279,500 KB
実行使用メモリ 35,284 KB
最終ジャッジ日時 2024-09-20 20:53:27
合計ジャッジ時間 6,954 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
12,264 KB
testcase_01 AC 15 ms
12,268 KB
testcase_02 AC 15 ms
12,272 KB
testcase_03 AC 16 ms
12,268 KB
testcase_04 AC 16 ms
12,140 KB
testcase_05 AC 16 ms
12,264 KB
testcase_06 AC 19 ms
12,276 KB
testcase_07 AC 51 ms
13,064 KB
testcase_08 AC 45 ms
13,060 KB
testcase_09 AC 71 ms
13,072 KB
testcase_10 AC 63 ms
12,308 KB
testcase_11 AC 86 ms
35,284 KB
testcase_12 AC 32 ms
12,288 KB
testcase_13 AC 70 ms
13,072 KB
testcase_14 AC 26 ms
12,668 KB
testcase_15 AC 24 ms
12,668 KB
testcase_16 AC 37 ms
13,060 KB
testcase_17 AC 62 ms
14,448 KB
testcase_18 AC 71 ms
13,200 KB
testcase_19 AC 70 ms
13,944 KB
testcase_20 AC 16 ms
12,136 KB
testcase_21 AC 33 ms
12,292 KB
testcase_22 AC 17 ms
12,264 KB
testcase_23 AC 16 ms
12,272 KB
testcase_24 AC 15 ms
12,136 KB
testcase_25 AC 17 ms
12,180 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<atcoder/all>
#include<bits/stdc++.h>
using namespace atcoder;
using namespace std;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fin(a) return pt(a)
using ll=long long;
using ld=long double;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using pll=pair<ll,ll>;
using mll=map<ll,ll>;
ll inf=1LL<<60;
ld pi=acos(-1);
ld eps=1e-10;
template<class T>using ascending_priority_queue=std::priority_queue<T,vector<T>,greater<T>>;
template<class T>using descending_priority_queue=std::priority_queue<T>;
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(b<a){a=b;return 1;}return 0;}
template<class V,class T>T max(vector<V>&vec,const T&id){T r=id;for(auto&v:vec)chmax(r,max(v,id));return r;}
template<class V,class T>T min(vector<V>&vec,const T&id){T r=id;for(auto&v:vec)chmin(r,min(v,id));return r;}
template<class T>pll mima(const T&a,const T&b){return {min(a,b),max(a,b)};}
template<class T>T sum(vector<T>&a){return accumulate(all(a),T(0));}
template<class T>T popcnt(T a){return __builtin_popcountll(a);}
istream&operator>>(istream&is,modint1000000007&x){unsigned int t;is>>t;x=t;return is;}
istream&operator>>(istream&is,modint998244353&x){unsigned int t;is>>t;x=t;return is;}
istream&operator>>(istream&is,modint&x){unsigned int t;is>>t;x=t;return is;}
ostream&operator<<(ostream&os,const modint1000000007&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint998244353&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint&x){os<<x.val();return os;}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<class T1,class T2>ostream&operator<<(ostream&os,const pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<class T>istream&operator>>(istream&is,vector<T>&v){for(T&x:v)is>>x;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&v){for(int i=0;i<(int)v.size();i++){os<<v[i]<<(i+1==(int)v.size()?"":" ");}return os;}
template<class...A>int pt_rest(){cout<<'\n';return 0;}
template<class...A>int pt(){cout<<'\n';return 0;}
template<class T,class...A>int pt_rest(const T&first,const A&...rest){cout<<" "<<first;pt_rest(rest...);return 0;}
template<class T,class...A>int pt(const T&first,const A&...rest){cout<<first;pt_rest(rest...);return 0;}
template<class V,class H>void resize(vector<V>&vec,const H head){vec.resize(head);}
template<class V,class H,class...T>void resize(vector<V>&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);}
template<class V,class T>void fill(V&x,const T&val){x=val;}
template<class V,class T>void fill(vector<V>&vec,const T&val){for(auto&v:vec)fill(v,val);}
template<class H>void vin(istream&is,const int idx,vector<H>&head){is>>head[idx];}
template<class H,class...T>void vin(istream&is,const int idx,vector<H>&head,T&...tail){vin(is>>head[idx],idx,tail...);}
template<class H,class...T>void vin(istream&is,vector<H>&head,T&...tail){for(int i=0;i<(int)head.size();i++)vin(is,i,head,tail...);}
template<class H,class...T>void vin(vector<H>&head,T&...tail){vin(cin,head,tail...);}
template<class H>void sin(istream&is,H&head){is>>head;}
template<class H,class...T>void sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);}
template<class H,class...T>void sin(H&head,T&...tail){sin(cin,head,tail...);}
void divisor(ll n,mll&div){for(ll i=1;i*i<=n;i++)if(n%i==0){div[i]++;div[n/i]++;}}
void factrization(ll n,mll&fact){for(ll i=2;i*i<=n;i++)while(n%i==0){fact[i]++;n/=i;}if(n>1)fact[n]++;}
ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while((r+1)<=x/(r+1))r++;return r;};
using S=ll;
S op(S a,S b){return a+b;}
S e(){return 0;}

struct SmallestPrimeFactor{
  v1 spf;//spf[i]:iを割り切る最小の素数
  v1 primes;
  SmallestPrimeFactor(ll N){//前処理
    spf.resize(N+1);
    for(ll i=0;i<=N;i++)spf[i]=i;//O(N)
    for(ll i=2;i*i<=N;i++)if(spf[i]==i)for(ll j=i+i;j<=N;j+=i)spf[j]=i;//O(NloglogN)
    for(ll i=2;i<=N;i++)if(spf[i]==i)primes.push_back(i);//O(N)
  }
  
  bool is_prime(ll n){assert(n+1<=spf.size());return spf[n]==n;}
  
  vector<pll>get_vec(ll n){//素因数分解クエリ
    vector<pll>res;
    while(n>1){//O(logN)
      if(res.empty() or res.back().first!=spf[n])
        res.emplace_back(spf[n],1);
      else
        res.back().second++;
      n/=spf[n];
    }
    return res;
  }
  mll get_map(ll n){//素因数分解クエリ
    mll res;
    while(n>1)res[spf[n]]++,n/=spf[n];//O(logN)
    return res;
  }
};

int main(void){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll N;cin>>N;
  vector<string>a(N),b(N);vin(a,b);
  
  SmallestPrimeFactor spf(1e6);
  two_sat ts(N);
  
  for(ll i=0;i<N;i++){
    for(ll j=0;j<N;j++){
      if(spf.is_prime(stoll(a[i]+a[j])))ts.add_clause(i,false,j,true);
      if(spf.is_prime(stoll(a[i]+b[j])))ts.add_clause(i,false,j,false);
      if(spf.is_prime(stoll(b[i]+a[j])))ts.add_clause(i,true,j,true);
      if(spf.is_prime(stoll(b[i]+b[j])))ts.add_clause(i,true,j,false);
    }
  }
  pt(ts.satisfiable()?"Yes":"No");
}
0