Submission #8533669

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1000100;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int N;
int arr[MAXN];
 
struct Dinic {
    struct Edge {
        int to, rev;
        ll c, f;
    };
    vi lvl, ptr, q;
    vector<vector<Edge>> adj;
    Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
    void addEdge(int a, int b, ll c, int rcap = 0) {
        adj[a].push_back({b, sz(adj[b]), c, 0});
        adj[b].push_back({a, sz(adj[a]) - 1, rcap, 0});
    }
    ll dfs(int v, int t, ll f) {
        if (v == t || !f) return f;
        for (int& i = ptr[v]; i < sz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1)
                if (ll p = dfs(e.to, t, min(f, e.c - e.f))) {
                    e.f += p, adj[e.to][e.rev].f -= p;
                    return p;
                }
        }
        return 0;
    }
    ll calc(int s, int t) {
        ll flow = 0; q[0] = s;
        rep(L,0,31) do { // 'int L=30' maybe faster for random data
            lvl = ptr = vi(sz(q));
            int qi = 0, qe = lvl[s] = 1;
            while (qi < qe && !lvl[t]) {
                int v = q[qi++];
                trav(e, adj[v])
                    if (!lvl[e.to] && (e.c - e.f) >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
            }
            while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
        } while (lvl[t]);
        return flow;
    }
};

bool pr (int x)
{
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    vector <int> v;
    for (int i = 0; i < N; i++)
    {
        if (i == 0 || arr[i-1] + 1 < arr[i])
            v.push_back(arr[i]);
        if (i == N - 1 || arr[i+1] - 1 > arr[i])
            v.push_back(arr[i]+1);
    }

    int m = v.size();
    Dinic d (m + 2);
    int ne = 0, no = 0;
    for (int i = 0; i < m; i++)
    {
        if (v[i] % 2 == 0)
        {
            d.addEdge (m, i, 1);
            ne++;
        }
        else
        {
            d.addEdge (i, m + 1, 1);
            no++;
        }
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
        {
            if (v[i] % 2 == 0 && v[j] % 2 == 1)
            {
                if (pr (abs (i - j)))
                    d.addEdge (i, j, 1);
            }
        }

    int r = d.calc (m, m + 1);

    int res = r;
    ne -= r;
    no -= r;
    res += 2 * (ne / 2 + no / 2);
    res += 3 * (ne % 2 + no % 2);
    cout << res << "\n";
}

Submission Info

Judge Result