fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. int mod =  1e9+7;
  6.  
  7. void solve()
  8. {
  9.     int n,l,r;
  10.  
  11.     cin>>n>>l>>r;
  12.  
  13.     int ls[n];
  14.     int rs[n];
  15.  
  16.     map<int,pair<int,int>> soc ; 
  17.  
  18.     for(int i=0;i<n;i++)
  19.     {
  20.         if(i+1<=l){
  21.             cin>>ls[i];
  22.             soc[ls[i]].first++;
  23.         }
  24.         else{
  25.             cin>>rs[i];
  26.             soc[rs[i]].second++;
  27.         }
  28.     }
  29.  
  30.     int tcost = 0;
  31.  
  32.     int pairs = 0;
  33.  
  34.     for(auto [x,y]:soc)
  35.     {
  36.         // tcost-=2*min(y.first,y.second);
  37.  
  38.         int minn=min(y.first,y.second);
  39.  
  40.         pairs+=minn;
  41.  
  42.         int f = y.first;
  43.         int s =y.second;
  44.  
  45.         auto it = soc.find(x);
  46.  
  47.         soc.erase(it);
  48.  
  49.         pair<int,int>p;
  50.  
  51.  
  52.  
  53.         p = make_pair(f-minn , s-minn);
  54.  
  55.         soc[x]=p; 
  56.     }
  57.  
  58.     int cntl=0,cntr=0;
  59.  
  60.  
  61.  
  62.     for(auto [x,y]:soc)
  63.     {
  64.         if(y.first)
  65.             cntl+=y.first;
  66.         else
  67.             cntr+=y.second;
  68.     }
  69.  
  70.     if(cntl == cntr){
  71.         cout<<cntr<<"\n";
  72.         return;
  73.     }
  74.  
  75.     tcost = abs(cntl -cntr)/2;
  76.  
  77.     vector<int> v;
  78.  
  79.     for(auto [x,y] : soc)
  80.     {
  81.         v.pb(y.first+y.second);
  82.     }
  83.  
  84.     int cnt=0;
  85.  
  86.     int extracost = (n- 2*pairs)/2;
  87.  
  88.     sort(v.begin(),v.end(),greater<int>());
  89.  
  90.  
  91.     for(auto x:v)
  92.     {
  93.         int bn = x/2;
  94.  
  95.  
  96.         if(bn+cnt > tcost){
  97.  
  98.             int lft = tcost  - cnt;
  99.  
  100.             extracost-=lft;
  101.             cnt+=1;
  102.             break;
  103.         }
  104.  
  105.         extracost-=bn;
  106.         cnt+=bn;
  107.  
  108.         if(cnt==tcost)
  109.             break;
  110.  
  111.     }
  112.  
  113.     cout<< extracost +  tcost<<"\n";
  114. }
  115.  
  116. int  main()
  117. {
  118.     int t=1;
  119.     cin>>t;
  120.  
  121.     while(t--)
  122.     {
  123.         solve();
  124.     }
  125. }
  126.  
  127.  
  128.  
Success #stdin #stdout 0s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/veYC42
language:
C++14 (gcc 8.3)
created:
2 years 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!