Advertisement
WayKillerZ

C - LIS Or Reversed LIS

May 22nd, 2022
832
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. #define II pair<int, int>
  5. #define III pair<int, pair<int, int>>
  6. #define DI pair<double, int>
  7. #define fs first
  8. #define sc second
  9. #define mp(a, b) make_pair(a, b)
  10. #define LINF 9223372036854775807
  11. #define INF 2147483647
  12.  
  13. using namespace std;
  14.  
  15. void solve() {
  16.  
  17.     int n, inp;
  18.     cin >> n;
  19.  
  20.     set<int> s, s2;
  21.     for(int i = 0; i < n; i++) {
  22.         cin >> inp;
  23.         if(s.count(inp) == 1) s2.insert(inp);
  24.         else s.insert(inp);
  25.     }
  26.  
  27.     vector<int> er;
  28.     int f = s.size();
  29.     for(auto& c : s) {
  30.         if(s.size() - er.size() <= s2.size()) break;
  31.         if(s2.count(c) == 0) {
  32.             s2.insert(c);
  33.             er.push_back(c);
  34.         }
  35.     }
  36.     for(int i = 0; i < er.size(); i++) {
  37.         s.erase(er[i]);
  38.     }
  39.  
  40.     cout << max(s.size(), s2.size()) << endl;
  41. }
  42.  
  43. int32_t main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.    
  47.     freopen("C.INP", "r", stdin);
  48.     freopen("C.OUT", "w", stdout);
  49.    
  50.     int t;
  51.     cin >> t;
  52.     while (t--) solve();  
  53.  
  54.     return 0;
  55. }
Advertisement
RAW Paste Data Copied
Advertisement