Submission #1489321

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef int in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct bipm{
  in n,m;
  VVI a;
  VI pr,vs;
  void ini(in pn, in pm){
    n=pn;
    m=pm;
    a.clear();
    a.resize(n);
    pr.clear();
    pr.resize(m,-1);
  }
  void ad(in u, in v){
    a[u].PB(v);
  }
  bool mm(in u){
    if(vs[u])
      return 0;
    vs[u]=1;
    in tt;
    forv(i,a[u]){
      tt=a[u][i];
      if(pr[tt]==-1){
	pr[tt]=u;
	return 1;
      }
      if(mm(pr[tt])){
	pr[tt]=u;
	return 1;
      }
    }
    return 0;
  }
  in mmat(){
    vs.resize(n);
    in sm=0;
    forn(i,n){
      forn(j,n)
	vs[j]=0;
      sm+=mm(i);
    }
    return sm;
  }
};
bipm mat;
bool isp(in a){
  if(a<=2)
    return 0;
  for(in i=2;i*i<=a;++i){
    if(a%i==0)
      return 0;
  }
  return 1;
}
in ab(in a){
  return a<0?-a:a;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  VI x(n);
  forn(i,n)
    cin>>x[i];
  VI lft,rgt;
  in c;
  forv(i,x){
    if(i==0 || x[i-1]+1!=x[i]){
      c=x[i];
      if(c%2==0)
	lft.PB(c);
      else
	rgt.PB(c);
    }
    if(i==n-1 || x[i]+1!=x[i+1]){
      c=x[i]+1;
      if(c%2==0)
	lft.PB(c);
      else
	rgt.PB(c);
    }
  }
  in l=sz(lft);
  in r=sz(rgt);
  mat.ini(l,r);
  forv(i,lft){
    forv(j,rgt){
      if(isp(ab(rgt[j]-lft[i])))
	mat.ad(i,j);
    }
  }
  c=mat.mmat();
  in res=c;
  l-=c;
  r-=c;
  assert(l%2==r%2);
  if(l%2){
    res+=3;
    --l;
    --r;
  }
  res+=l+r;
  cout<<res<<endl;
  return 0;
}

Submission Info

Judge Result