Epic Transformation Solution Codeforces Round #710 Div. 3

by

You are given an array aa of length nn consisting of integers. You can apply the following operation, consisting of several steps, on the array aa zero or more times:

  • you select two different numbers in the array aiai and ajaj;
  • you remove ii-th and jj-th elements from the array.

For example, if n=6n=6 and a=[1,6,1,1,4,4]a=[1,6,1,1,4,4], then you can perform the following sequence of operations:

  • select i=1,j=5i=1,j=5. The array aa becomes equal to [6,1,1,4][6,1,1,4];
  • select i=1,j=2i=1,j=2. The array aa becomes equal to [1,4][1,4].

What can be the minimum size of the array after applying some sequence of operations to it?Input

The first line contains a single integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) is length of the array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.Output

For each test case, output the minimum possible size of the array after applying some sequence of operations to it.ExampleinputCopy

5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1

outputCopy

0
0
2
1
0

Solution :

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long int ull;

typedef long long int ll;

typedef long double ld;

typedef vector<ll> vi;

typedef vector<pair<ll,ll>> vii;

typedef pair<ll,ll> pii;

typedef map<ll,ll> mii;

#define MOD7 1000000007

#define MOD9 1000000009

#define pi 3.1415926535

#define Test_cases ll TC;cin>>TC;while(TC–)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define pb push_back

#define mp make_pair

#define F first

#define S second

#define all(x) x.begin(),x.end()

#define rall(x) x.rbegin(), x.rend()

#define sp(x) fixed<<setprecision(x)

#define sz(x) (ll)(x.size())

#define fo(i,a,b) for(i=a;i<b;i++)

#define foe(i,a,b) for(i=a;i<=b;i++)

const ll INF = (ll)2e18 + 77;

void solve()

{

int n,i;cin>>n;

int a[n];

fo(i,0,n)cin>>a[i];

unordered_map<int,int>M;

fo(i,0,n)M[a[i]]++;

priority_queue<int>pq;

for(auto it:M)

{

pq.push(it.S);

}

int ans=0;

while(sz(pq)>1)

{

int p=pq.top();pq.pop();

int q=pq.top();pq.pop();

ans++;

p–;

q–;

if(p)pq.push(p);

if(q)pq.push(q);

}

cout<<n-2*ans<<“\n”;

}

int main()

{

fastio

Test_cases

solve();

return 0;

}

Leave a Comment