fork(2) download
  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
stdin
Standard input is empty
stdout
Standard output is empty