fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5. #define int long long
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9. #define all(x) (x).begin(), (x).end()
  10. #define rall(x) (x).rbegin(), (x).rend()
  11. #define sz(x) ((int)(x).size())
  12. #define endl '\n'
  13. #define yes cout << "yes\n"
  14. #define no cout << "no\n"
  15.  
  16. #define rep(i,a,b) for(int i=a;i<b;++i)
  17. #define per(i,a,b) for(int i=b-1;i>=a;--i)
  18. #define each(x, a) for (auto& x : a)
  19.  
  20. const int INF = 1e18;
  21. const int MOD = 1e9+7;
  22. const int N = 2e5 + 5;
  23.  
  24. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  25. int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
  26. int power(int a, int b, int m = MOD) {
  27.     int res = 1;
  28.     while (b > 0) {
  29.         if (b & 1) res = res * a % m;
  30.         a = a * a % m;
  31.         b >>= 1;
  32.     }
  33.     return res;
  34. }
  35. int modinv(int a, int m = MOD) {
  36.     return power(a, m - 2, m);
  37. }
  38.  
  39. void solve() {
  40.     int n;
  41.     cin >> n;
  42.     vector<int> a(n), sorted_a(n);
  43.     rep(i, 0, n) {
  44.         cin >> a[i];
  45.         sorted_a[i] = a[i];
  46.     }
  47.  
  48.     sort(all(sorted_a));
  49.     int M = sorted_a[n / 2];
  50.  
  51.     vector<int> P_less(n + 1, 0), P_greater(n + 1, 0);
  52.     rep(i, 0, n) {
  53.         P_less[i + 1] = P_less[i] + (a[i] < M);
  54.         P_greater[i + 1] = P_greater[i] + (a[i] > M);
  55.     }
  56.  
  57.     vector<int> dp(n + 1, -1);
  58.     dp[0] = 0;
  59.  
  60.     rep(i, 1, n + 1) {
  61.         for (int j = (i % 2 == 1 ? 0 : 1); j < i; j += 2) {
  62.             if (dp[j] != -1) {
  63.                 int len = i - j;
  64.                 int c_less = P_less[i] - P_less[j];
  65.                 int c_greater = P_greater[i] - P_greater[j];
  66.  
  67.                 if (c_less <= len / 2 && c_greater <= len / 2) {
  68.                     dp[i] = max(dp[i], dp[j] + 1);
  69.                 }
  70.             }
  71.         }
  72.     }
  73.  
  74.     cout << dp[n] << endl;
  75. }
  76.  
  77. int32_t main() {
  78.     fast_io;
  79.  
  80.     int t;
  81.     cin >> t;
  82.     while (t--) {
  83.         solve();
  84.     }
  85.  
  86.     return 0;
  87. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10
5
3 3 2 4 3
7
9 5 7 7 4 7 7
9
1 1 1 1 1 1 1 1 1
1
5
3
1 2 3
3
2 2 2
5
1 2 3 4 5
5
2 1 3 2 2
7
2 2 1 2 3 2 2
9
2 1 2 3 2 1 2 3 2
stdout
copy 
3
3
9
1
1
3
1
3
5
5
https://ideone.com/bvbQcU
language:
C++ (gcc 8.3)
created:
5 hours 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!