1515D - Phoenix and Socks - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(v) v.begin(), v.end()
#define int long long
#define ll long long
#define pb push_back
#define endl "\n"
#define bn begin()
#define en end()
#define ppb pop_back
#define ff first
#define ss second
#define pii pair<int, int>
#define loop(i, a, b) for (int i = a; i < b; i++)
#define bs binary_search
const ll inf = 1e18, mod = 1e9 + 7;
#define add_mod(a, b) (a % mod + b % mod) % mod
#define mul_mod(a, b) (a % mod * b % mod) % mod
#define sub_mod(a, b) (mod + a % mod - b % mod) % mod
#define compar \
    bool compare(int a, int b) { return a > b; }
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    #define file  freopen("Error.txt", "w", stderr);freopen("input.txt", "r", stdin ); freopen("output.txt", "w", stdout);
#else
    #define file
#endif
#define per(x) fixed << setprecision(x) << // syntax:-cout<<per(jitni decimal place chahiyaen)variable name;
// bool compare(pair<int,int> a,pair<int,int> b){if(a.first==b.first)return a.second<b.second;return a.first<b.first;}
// if an element have a divisor i less than sqrt(n) the it will definately have n/i as a divisor
//  (a/b) %m = a%m *binpow(b,m-2) provided b and m are co-prime.
//  negative number ka mod tackle karne ke liyaen uss number me mod jod kar mod kar lo
int binpow(int a, int b)
{
    int res = 1LL;
    while (b > 0)
    {
        if (b & 1)
            res = (res%mod * a%mod)%mod;
        a = (a%mod * a%mod)%mod;
        b >>= 1;
    }
    return res;
}
int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}
int lcm(int a,int b)
{
    return ((a*b)/gcd(a,b));
}
int ceil_div(int a,int b)
{
    int val = (a / b) + ((a % b) != 0ll);
    return val;
}
int modinv(int a, int m)
{
    int m0 = m;
    int y = 0LL, x = 1LL;
    if (m == 1LL)
        return 0LL;
    while (a > 1LL)
    {
        int q = a / m;
        int t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0LL)
        x += m0;

    return x;
}

void printDivisors(int n, vector<int> &v)
{
    // vector<int> v;
    // Note that this loop runs till square root
    for (int i = 1; i*i <= n; i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, print only one
            if (n / i == i)
                v.pb(i);

            else
            { // Otherwise print both
                // if (i != 1)
                    v.pb(i);
                v.pb(n / i);
            }
        }
    }
}
// vector<int> x={0,0,1,-1};
// vector<int> y={-1,1,0,0};
// vector<char> path={'L','R','D','U'};
// vector<int> x={0,0,1,-1,1,1,-1,-1};
// vector<int> y={1,-1,0,0,1,-1,1,-1};

// everyday 1 codeforces and 1 leetcode in the morning  
// everyday 1 codeforces and 1 leetcode in the evening
// always take the input correctly.

// if p divides x+k and y+k the p also devides (y-x) for (y>x)
// (a|x)-(b&x) == (a|x) ^ (b&x)
// if a%b==0 then a must contain contain all the prime factors of b in same or greater freq. along with other prime numbers
// for interactive problem make sure ki (#define endl as "\n") ko comment out karke endl likho
// when even we are ask find in each sub array or subseq try to find how an individual element is contributing in the final answer of

void fun()
{
    int n,l,r;
    cin>>n>>l>>r;
    map<int,int> m;
    loop(i,0,l)
    {
        int a;
        cin>>a;
        m[a]++;
    }
    loop(j,0,r)
    {
        int a;
        cin>>a;
        m[a]--;
    }
    int ol=0;
    int el=0;
    int odr=0;
    int er=0;
    int ct=0;
    for(auto it: m)
    {
        if(it.ss<0)
        {
            if(it.ss%2)
            {
                odr++;
                er+=max(abs(it.ss)-1ll,0ll);
            }
            else
            {
                er+=abs(it.ss);
            }
        }
        else
        {
            if(it.ss%2)
            {
                ol++;
                el+=max(it.ss-1ll,0ll);
            }
            else
            {
                el+=it.ss;

            }   
        }
    }
    int ans=min(ol,odr);
    ol-=ans;
    odr-=ans;
    if(ol!=0)
    {
        int a=min(er,ol);
        ans+=a;
        er-=a;
        ol-=a;
    }

    if(odr!=0)
    {
        int a=min(el,odr);
        ans+=a;
        el-=a;
        odr-=a;
    }
    ans+=(ol+odr+er/2+el/2);
    cout<<ans<<endl;
    // cout<<ol<<" "<<el<<" "<<odr<<" "<<er<<endl;
}

signed main()
{
    fast 
    file
    int t;
    cin >> t;
    // t=1;
    while (t--)
    {
        fun();
    }
    return 0;
}