Advertisement
ivnikkk

Untitled

Dec 4th, 2021
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. using namespace std;
  18. typedef long long              ll;
  19. typedef unsigned long long     ull;
  20. typedef long double            ld;
  21. #define sqrt              sqrtl
  22. #define endl              "\n"
  23. #define all(a)            a.begin(), a.end()
  24. #define allr(a)           a.rbegin(), a.rend()
  25. #define pb                push_back
  26. #define F                 first
  27. #define S                 second
  28. //3
  29. //4
  30. //4 4 4 4
  31. //0
  32. //4
  33. //1 2 4 4
  34. //1
  35. void solve() {
  36. }
  37.  
  38. signed main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.     ll t = 1;
  42.     cin >> t;
  43.     //ll iff = 0;
  44.     //1 1 2 1 4 4 1
  45.     while (t--) {
  46.         ll n;
  47.         cin >> n;
  48.         vector<vector<ll>>dp(n, vector<ll>(201,0));
  49.         vector<ll>a(n);
  50.         for (ll i = 0; i < n; i++)
  51.             cin >> a[i];
  52.         ll cur = 200;
  53.         dp[0][a[0]]++;
  54.         ll count = 0;
  55.         for (ll i = 1; i < n; i++) {
  56.             for (ll j = 1; j <= cur; j++) {
  57.                 dp[i][j] = dp[i - 1][j] + (a[i] == j);
  58.             }
  59.         }
  60.         for (ll i = 1; i <= cur; i++) {
  61.             if (dp[n - 1][i])
  62.                 count++;
  63.         }
  64.         if (count == n) {
  65.             cout << 1 << endl;
  66.             continue;
  67.         }
  68.         if (count == 1) {
  69.             for (ll i = 1; 1 <= cur; i++) {
  70.                 if (dp[n - 1][i]) {
  71.                     //cout << "case #" << iff << ' ';
  72.                     cout << dp[n - 1][i] << endl;
  73.                     //iff++;
  74.                     break;
  75.                 }
  76.             }
  77.             continue;
  78.         }
  79.         else if (count == 2) {
  80.             ll cnt = 0;
  81.             ll loll = -1;
  82.             for (ll i = 1; i < n; i++) {
  83.                 if (a[i] != a[i - 1]) {
  84.                     cnt++;
  85.                     loll = max(dp[n - 1][a[i]], dp[n - 1][a[i - 1]]);
  86.                     i ++;
  87.                 }
  88.             }
  89.             if (cnt == 1) {
  90.                 //cout << "case #" << iff<<' ';
  91.                 cout<<  loll << endl;
  92.                 //iff++;
  93.                 continue;
  94.             }
  95.         }
  96.         ll mx = -1;
  97.         for (ll i = 0; i < n; i++) {
  98.             for (ll j = 1; j <= cur; j++) {
  99.                 ll check = dp[n - 1][j] - 2 * dp[i][j];
  100.                 if (dp[n - 1][j] - 2 * dp[i][j] >= 0) {
  101.                     ll l = i, r = n;
  102.                     while (r - l > 1) {
  103.                         ll mid = (r + l) / 2;
  104.                         if (dp[mid][j] - 2*dp[i][j] >= 0) {
  105.                             r = mid;
  106.                         }
  107.                         else l = mid;
  108.                     }
  109.                     ll mex = -1;
  110.                     for (ll f = 1; f <= cur; f++) {
  111.                         if(f!=j)
  112.                         mex = max(dp[l][f] - dp[i][f], mex);
  113.                     }
  114.                     mx = max(mex + 2 * dp[i][j], mx);
  115.                 }
  116.             }
  117.         }
  118.         //cout << "case #" << iff << ' ';
  119.         cout << mx << endl;
  120.        // iff++;
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement