Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1615
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1615
Insatisfaction on Elections
By Bruno Adami, Universidade de São Paulo - São Carlos 
Brazil
Timelimit: 1
An election was made in a small town of M citizens, where there were N candidates. People would write the candidate number in a piece of paper, and then they put it in a closed box.
At the end of the election, if a candidate receives a quantity strictly greater than 50% of the votes, he is considered the winner. Otherwise a second round of elections will happen.
As the manual counting process is very slow, you must write an algorithm that decides whose candidate is the winner or if none of them received enough votes and a second round is needed.
Input
The first line contains an integer T (T ≤ 100) indicating the number of test cases.
For each test case, on the first line you will have the integers N (1 ≤ N ≤ 10) and M. On the following line, M (1 ≤ M ≤ 103* or 1 ≤ M ≤ 5*104**) integers will follow separated by spaces, indicating the candidate that each citizen voted for, it is, the number that was writen in each piece of paper inside the closed box.
*For around 90% of the cases;
**For the other cases.
Output
For each test case, print the winning candidate, or -1 in the case of a second round of elections.
| Sample Input | Sample Output |
|
3 2 3 1 1 2 2 5 1 2 2 1 2 3 4 1 2 3 1 |
1 2 -1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define MAXV 200100
using namespace std;
typedef vector<int> vi;
typedef pair < int, int> ii;
typedef long long int64;
typedef pair < int, string> is;
int readInt()
{
bool minus = false;
int result = 0;
char ch;
ch = getchar_unlocked();
while (true) {
if (ch == '-')
break;
if (ch >= '0' && ch < = '9')
break;
ch = getchar_unlocked();
}
if (ch == '-')
minus = true;
else
result = ch - '0';
while (true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result * 10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
int main()
{
ios::sync_with_stdio(false);
int a, b, c, t;
t = readInt();
while (t--) {
a = readInt();
b = readInt();
unordered_map < int, int> election;
for (int i = 0; i < b; i++) {
c = readInt();
if (election.count(c))
election[c]++;
else
election.insert(mp(c, 1));
}
unordered_map < int, int>::iterator it;
int winner = 0, count = 0;
for (it = election.begin(); it != election.end(); it++) {
if (it->second > count) {
count = it->second;
winner = it->first;
}
}
if (count > b / 2)
cout << winner << endl;
else
cout << -1 << endl;
}
return 0;
}
Input
2 3
1 1 2
2 5
1 2 2 1 2
3 4
1 2 3 1
Output
2
-1