fork download 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. //#pragma GCC optimize("unroll-loops")
  10. //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
  11. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  12. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  13. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  14. #define fi first
  15. #define se second
  16. #define M 1000000007
  17. #define MAXN 2000001
  18. #define INF (1ll<<30)
  19. #define BLOCK_SIZE 425
  20. #define MAX_NODE 1001001
  21. #define LOG 19
  22. #define ALPHA_SIZE 26
  23. #define BASE 256
  24. #define NAME "file"
  25. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  26. using namespace std;
  27. using namespace chrono ;
  28. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  29. const ll NMOD = 1;
  30. const int dx[] = {-1, 0, 1,0};
  31. const int dy[] = {0, 1, 0, -1};
  32. //**Variable**//
  33. ll n ;
  34. pair<ll,ll>  arr[MAXN];
  35. vector<pair<ll,ll>>le, chan ;
  36. vector<ll>pos1  ;
  37. vector<ll> value[MAXN] ;
  38. vector<pair<ll,ll> > res ;
  39. vector<ll> adj[MAXN] ;
  40. ll prime[MAXN] ;
  41. void sang() {
  42.     memset(prime, 1, sizeof prime ) ;
  43.     prime[0] = prime[1] = false ;
  44.  
  45.     for(long long i = 2 ; i * i < MAXN ; i ++ ) for(ll j = i * i ; j < MAXN ; j += i ) prime[j] = false ;
  46. }
  47. //**Struct**//
  48.  
  49. //**Function**//
  50. template<class X, class Y >
  51. bool minimize(X & x, const Y &y ) {
  52.     return x > y ? x = y, 1:0 ;
  53. }
  54. template<class X, class Y >
  55. bool maximize(X &x, const Y &y ) {
  56.     return x < y ? x = y, 1:0 ;
  57. }
  58. bool used[MAXN] ;
  59. void init() {
  60.     cin>>n;
  61.     FOR(i,1, n) cin >> arr[i].fi, arr[i].se = i;
  62. //    sort(arr + 1 ,   arr + n + 1 ) ;
  63. }
  64. ll matchL[MAXN], matchR[MAXN], seen[MAXN], time_kuhn = 0 ;
  65. bool kuhn(ll u ) {
  66.     if(seen[u] == time_kuhn) return false;
  67.     else seen[u] = time_kuhn ;
  68.     for(ll v : adj[u])if( ( matchR[v] == -1 || kuhn(matchR[v]) ) ) {
  69.             matchL[u] = v ;
  70.             matchR[v] = u ;
  71.             return true ;
  72.         }
  73.     return false ;
  74. }
  75. void solve_sub123() {
  76.     vector<ll> leftt, rightt, ones ;
  77.     FOR(i,1,n) {
  78.         if(arr[i].fi == 1 ) ones.push_back(i)  ;
  79.         else  if (arr[i].fi % 2 == 1) leftt.push_back(arr[i].se);
  80.         else rightt.push_back(arr[i].se);
  81.     }
  82.  
  83.     memset(matchL, -1, sizeof matchL ) ;
  84.     memset(matchR, -1, sizeof matchR ) ;
  85.     for (ll u : leftt) {
  86.         for (ll v : rightt) {
  87.             if ( prime[arr[u].fi + arr[v].fi]) {
  88.                 adj[u].push_back(v);
  89.             }
  90.         }
  91.     }
  92.  
  93.     for(ll u : leftt) {
  94.         time_kuhn++;
  95.         kuhn(u);
  96.     }
  97.  
  98.     for (ll u : ones) {
  99.         for (ll v : rightt) {
  100.             if ( prime[arr[u].fi + arr[v].fi]) {
  101.                 adj[u].push_back(v);
  102.             }
  103.         }
  104.     }
  105.     for(ll u : ones ) {
  106.         time_kuhn++;
  107.         kuhn(u);
  108.     }
  109.  
  110.     for (ll u : leftt) {
  111.         if (matchL[u] != -1 && !used[u] && !used[matchL[u]]) {
  112.             res.push_back({u, matchL[u]});
  113.             used[u] = used[matchL[u]] = true;
  114.         }
  115.     }
  116.  
  117.  
  118.     for (ll u : ones)if (matchL[u] != -1 && !used[u] && !used[matchL[u]]) {
  119.             res.push_back({u, matchL[u]});
  120.             used[u] = used[matchL[u]] = 1;
  121.         }
  122.     for (ll u : ones) if (!used[u] && matchL[u] == -1) pos1.push_back(u);
  123.     ll last = -1  ;
  124.     for(ll p : pos1 ) {
  125.         if(last == -1 ) last = p ;
  126.         else {
  127.             res.push_back({last, p }) ;
  128.             used[p] = used[last] = true ;
  129.             last = -1  ;
  130.         }
  131.     }
  132.     cout << res.size() << el ;
  133.     for(auto[u, v ] : res ) cout << u << " " << v << el ;
  134. }
  135. void  get(ll l, ll r ) {
  136.     while (l < r ) {
  137.         res.push_back( { arr[l].se, arr[r].se }  ) ;
  138.         l ++ ;
  139.         r -- ;
  140.     }
  141. }
  142. void solve_sub4() {
  143.     vector<pair<ll,ll> > pos;
  144.  
  145. //    FOR(i, 1, n) pos.push_back({arr[i], i });
  146.     FOR(i, 1,  n  ) pos.push_back({arr[i].fi, i     }) ;
  147.     sort(pos.begin(), pos.end());
  148.  
  149.     vector<pair<ll,ll> > ans;
  150.     ll r = n - 1;
  151.     while (r > 0) {
  152.         ll l = -1;
  153.         for (ll i = 0; i < r; i++)
  154.             if (prime[pos[i].fi + pos[r].fi]) {
  155.                 l = i;
  156.                 break;
  157.             }
  158.         if (l == -1) {
  159.             --r;
  160.             continue;
  161.         }
  162.         ll l1 = l, rr = r;
  163.         while (l1 < rr) {
  164.             ans.push_back({pos[l1].se, pos[rr].se});
  165.             ++l1;
  166.             --rr;
  167.         }
  168.         r = l - 1;
  169.     }
  170.     cout << ans.size() << el;
  171.     for (auto &p : ans) cout << p.fi << " " << p.se << el ;
  172.     return ;
  173. }
  174.  
  175. __ROOT__ {
  176.     // freopen(NAME".inp" , "r" , stdin);
  177.     // freopen(NAME".out" , "w", stdout) ;
  178.     fast;
  179.     sang();
  180.     int t = 1; // cin >> t ;
  181.     while(t--) {
  182.         init();
  183.         if(n <= 1000 ) solve_sub123();
  184.         else
  185.             solve_sub4() ;
  186.     }
  187.     return (0&0);
  188. }
  189.  
Success #stdin #stdout 0.06s 124364KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/gK6477
language:
C++14 (gcc 8.3)
created:
23 days ago
visibility:
public

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!