fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define yes cout << "YES\n";
  6. #define no cout << "NO\n";
  7.  
  8.  
  9. void FastIO() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     cout.tie(nullptr);
  13. }
  14.  
  15. void solve(){
  16.     int n,l,r;
  17.     cin >> n >> l >> r;
  18.  
  19.     map<int,int>freql,freqr;
  20.  
  21.     for(int i = 0; i < n; i++){
  22.         int x;
  23.         cin >> x;
  24.  
  25.         if(i < l)
  26.             freql[x]++;
  27.         else
  28.             freqr[x]++;
  29.     }
  30.  
  31.     int mn = min(l,r), cost = n/2 - mn, matched = 0, cnt = cost;
  32.  
  33.     if(l > r){
  34.         for(auto &p : freql){
  35.             if(cnt == 0)
  36.                 break;
  37.             if(p.second > 1){
  38.                 freqr[p.first]++;
  39.                 freql[p.first]--;
  40.                 cnt--;
  41.             }
  42.         }
  43.         if(cnt > 0){
  44.             for(auto &p : freql){
  45.                 if(cnt == 0)
  46.                     break;
  47.                 freqr[p.first]++;
  48.                 freql[p.first]--;
  49.                 cnt--;
  50.             }
  51.         }
  52.     }
  53.     else if(l < r){
  54.         for(auto &p : freqr){
  55.             if(p.second > 0){
  56.                 if(cnt == 0)
  57.                     break;
  58.                 freql[p.first]++;
  59.                 freqr[p.first]--;
  60.                 cnt--;
  61.             }
  62.         }
  63.         if(cnt > 0){
  64.             for(auto &p : freqr){
  65.                 if(cnt == 0)
  66.                     break;
  67.                 freql[p.first]++;
  68.                 freqr[p.first]--;
  69.                 cnt--;
  70.             }
  71.         }
  72.     }
  73.  
  74.     for(auto &p : freql){
  75.         if(freqr[p.first] > 1){
  76.             matched++;
  77.             freqr[p.first]--;
  78.         }
  79.     }
  80.  
  81.     cost += n/2 - matched;
  82.  
  83.     cout << cost << '\n';
  84. }
  85.  
  86.  
  87. signed main(){
  88.     FastIO();
  89.  
  90.     int t = 1;
  91.     cin >> t;
  92.  
  93.     while (t--){
  94.         solve();
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3
stdout
copy 
2
3
5
3
https://ideone.com/AfWoOs
Phoenix and socks
language:
C++14 (gcc 8.3)
created:
8 days 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!