fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 200005
  7. #define mins 1005
  8. #define eps 0.000000000001
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pll,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32.  
  33.  
  34. int n1, n2;
  35. int matching[maxs], dist[maxs];
  36. bool used[maxs], vis[maxs];
  37. vector<int>adj[maxs];
  38. queue<int>Q;
  39. map<int,int>mp;
  40. int ans1[maxs];
  41. vector<int>v,v1,v2;
  42.  
  43. void init(int _n1, int _n2) {
  44.     n1 = _n1;
  45.     n2 = _n2;
  46. }
  47.  
  48. void bfs() {
  49.     fill(dist, dist + n1, -1);
  50.     for(int i=0;i<n1;i++){
  51.         if(!used[i]){
  52.             Q.push(i);
  53.             dist[i]=0;
  54.         }
  55.     }
  56.     while(!Q.empty()){
  57.         int u=Q.front();
  58.         Q.pop();
  59.         for(int i=0;i<adj[u].size();i++){
  60.             int v=adj[u][i];
  61.             int u2=matching[v];
  62.             if(u2>=0 && dist[u2]<0){
  63.                 dist[u2]=dist[u]+1;
  64.                 Q.push(u2);
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. bool dfs(int u1) {
  71.     vis[u1] = true;
  72.     for(int i=0;i<adj[u1].size();i++){
  73.         int v=adj[u1][i];
  74.         int u2=matching[v];
  75.         if(u2<0 || !vis[u2] && dist[u2]==dist[u1]+1 && dfs(u2)){
  76.             matching[v]=u1;
  77.             used[u1]=true;
  78.             return true;
  79.         }
  80.     }
  81.     return false;
  82. }
  83.  
  84. int maxMatching() {
  85.     fill(used, used + n1, false);
  86.     fill(matching, matching + n2, -1);
  87.     for (int res = 0;;){
  88.         bfs();
  89.         fill(vis, vis + n1, false);
  90.         int f=0;
  91.         for(int i=0;i<n1;i++){
  92.             if(!used[i] && dfs(i)){
  93.                 f++;
  94.             }
  95.         }
  96.         if(!f){
  97.             return res;
  98.         }
  99.         res+=f;
  100.     }
  101. }
  102.  
  103. int mark[200005];
  104. int vis1[3005],vis2[3005];
  105.  
  106. int main()
  107. {
  108.     int n,i,j,x;
  109.     sc("%d",&n);
  110.     for(i=0;i<n;i++){
  111.        sc("%d",&x);
  112.        if(x&1){
  113.             v1.pb(x);
  114.        }
  115.        else{
  116.             v2.pb(x);
  117.        }
  118.     }
  119.     sort(v1.begin(),v1.end());
  120.     sort(v2.begin(),v2.end());
  121.     reverse(v1.begin(),v1.end());
  122.     for(i=2;i<maxs;i++){
  123.        if(!mark[i]){
  124.             for(j=i*2;j<maxs;j+=i){
  125.                 mark[j]=1;
  126.             }
  127.         }
  128.     }
  129.     int tans=0;
  130.     if(v1.size()!=0){
  131.         if(v1[v1.size()-1]==1){
  132.             int fl=0;
  133.             for(j=0;j<v2.size();j++){
  134.                 if(mark[1+v2[j]]==0){
  135.                    fl=1;
  136.                 }
  137.             }
  138.             if(!fl){
  139.                 tans++;
  140.                 n--;
  141.                 v1.pop_back();
  142.             }
  143.         }
  144.     }
  145.     init(v1.size(),v2.size());
  146.     for(i=0;i<v1.size();i++){
  147.         for(j=0;j<v2.size();j++){
  148.             if(mark[v1[i]+v2[j]]==0){
  149.                 adj[i].pb(j);
  150.                 vis2[j]=1;
  151.                 vis1[i]=1;
  152.             }
  153.         }
  154.     }
  155.     int fl=0;
  156.     for(i=0;i<v1.size();i++){
  157.         if(vis1[i]==0){
  158.             fl=1;
  159.         }
  160.     }
  161.     for(i=0;i<v2.size();i++){
  162.         if(vis2[i]==0){
  163.             fl=1;
  164.         }
  165.     }
  166.     if(fl==1){
  167.         pr("-1\n");
  168.         return 0;
  169.     }
  170.     int ans=maxMatching();
  171.     tans+=(n-ans);
  172.     pr("%d\n",tans);
  173.     return 0;
  174. }
Success #stdin #stdout 0s 9360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Ky5GaP
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!