Return to Revisions

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 <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
struct voter
{
 string name;
 int numvotes;
 bool operator==(const string &) const;
 bool operator<(const voter &) const;
 bool operator>(const voter &) const;
};
bool voter::operator==(const string &f) const
{
 return name == f;
}
bool voter::operator<(const voter &f) const
{
 return (numvotes < f.numvotes);
}
bool voter::operator>(const voter &f) const
{
 return (numvotes > f.numvotes);
}
bool myfunction(voter i, voter j) { return (i<j); }
int main() {
 vector<voter> voters;
 string name;
 while (getline(cin, name))
 {
 if (name == "***")
 {
 break;
 }
 _Vector_iterator<_Vector_val<_Simple_types<voter>>> it = find(voters.begin(), voters.end(), name);
 if (it != voters.end()) {
 it->numvotes += 1;
 }
 else
 {
 voter a;
 a.name = name;
 a.numvotes = 1;
 voters.push_back(a);
 }
 }
 sort(voters.begin(), voters.end(), greater<voter>());
 
 if (voters[0].numvotes == voters[1].numvotes)
 {
 cout << "Runoff!" << endl;
 }
 else
 {
 _Vector_iterator<_Vector_val<_Simple_types<voter>>> tt = max_element(voters.begin(), voters.end());
 cout << tt->name << endl;
 }
 return 0;
}

My program will pass all of the tests except the very last one where it "times out". Any input I can get on this will be greatly appreciated. This code does compile and run in VS and here: http://cpp.sh/8l3b

To get this to run on cpp.sh I did have to change the _Vector_iterator<_Vector_val<_Simple_types<voter>>> on lines 43 and 63 to auto. I don't quite understand why, so I would also be very appreciative if you could explain what I should use as a type to be portable.