Kattis Challenge - Recount - count who has the most votes in a list of names

I am attempting to solve the Kattis problem Recount.


The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge!


In their desperation, the election officials turn to you and ask you to write a program to count the vote!

Input


The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least 2 votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to 100,000 valid votes.

Output


If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: “Runoff!” (don’t forget to include the exclamation mark!)

Sample Input 1

Penny Franklin  
Marti Graham  
Connie Froggatt  
Joseph Ivers  
Connie Froggatt  
Penny Franklin  
Connie Froggatt  
Bruce Stanger  
Connie Froggatt  
Barbara Skinner  
Barbara Skinner  
***

Sample Output 1

Connie Froggatt

Sample Input 2

Penny Franklin  
Connie Froggatt  
Barbara Skinner  
Connie Froggatt  
Jose Antonio Gomez-Iglesias  
Connie Froggatt  
Bruce Stanger  
Barbara Skinner  
Barbara Skinner
***

Sample Output 2

Runoff!

```
#include
#include
#include
#include
#include
using namespace std;

struct voter
{
string name;
int numvotes;
bool operator

There are 2 important performance issues here:

-
find(...) in a vector performs a linear search, \$O(n)\$. You would do better by using a hash map instead, that would allow constant-time search, \$O(1)\$.

-
Sorting the candidates by vote count is unnecessary to find the ones with the maximum count. Sorting is an \$O(n \log n)\$ operation. You can find the maximum with a linear search, \$O(n)\$, and in a second linear pass you could verify if a run-off is needed. (You could as well make this part of step 1 and do it in a single pass, but that wouldn't change the order of complexity of the algorithm.)

Lastly, a minor thing, but the implementation will fail if there are less than two candidates :-)

StackExchange Code Review Q#156928, answer score: 4