fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) x.begin(), x.end()
  3. #define dbg(x) cerr << #x << " = " << x << endl
  4. #define _ << ' ' <<
  5. using namespace std;
  6. using ll = long long;
  7. using vi = vector<int>;
  8. using ii = pair<int, int>;
  9. using vii = vector<ii>;
  10.  
  11. set<int> g[300000];
  12. vi h;
  13. int p[300000], q[300000];
  14.  
  15. int main()
  16. {
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(0);
  19.     int n = 300000;
  20.     int m = n/2;
  21.     for (int i = 0; i < n; ++i)
  22.     {
  23.         p[i] = (i+1);
  24.         p[i]--;
  25.         q[p[i]] = i;
  26.     }
  27.  
  28.     for (int i = 0; i < m; ++i)
  29.     {
  30.         int u, v;
  31.         u = (i+1);
  32.         v = n;
  33.         g[v - 1].insert(u - 1);
  34.         if (v - 1 == p[n - 1])
  35.             h.push_back(u - 1);
  36.     }
  37.  
  38.     sort(all(h), [](int a, int b) { return q[a] > q[b]; });
  39.     int pos = n - 1, sol = 0;
  40.     vi bad;
  41.     for (int x : h)
  42.     {
  43.         for (int i = q[x] + 1; i < pos; ++i)
  44.             bad.push_back(p[i]);
  45.  
  46.         bool good = true;
  47.         for (int y : bad)
  48.             if (g[y].find(x) == g[y].end())
  49.                 good = false;
  50.  
  51.         if (!good)
  52.             break;
  53.  
  54.         sol++;
  55.         pos = q[x];
  56.     }
  57.     cout << sol;
  58. }
Success #stdin #stdout 0.02s 38792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fpYDyS
language:
C++14 (gcc 8.3)
created:
5 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!