fork(1) download
copy 
  1. #include <math.h>
  2. #include <string.h>
  3. #include <iostream>
  4. #include <string>
  5. #include <fstream>
  6. #include <unordered_map>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <iomanip>
  10.  
  11. using namespace std;
  12.  
  13. typedef pair<string, bool> candidate;
  14. typedef pair<int, int> candidateId;
  15.  
  16. void tokenizeString(const string &str, vector<string>& tokens, const string &delimiters);
  17. bool candidateIdCompare(const candidateId &c1, const candidateId &c2);
  18. bool isStringEmptyOrWhitespace(string str);
  19.  
  20. const int CANDIDATE_MAX_COUNT = 20;
  21. const int BALLOT_MAX_COUNT = 1000;
  22.  
  23. candidate candidates[CANDIDATE_MAX_COUNT];
  24. vector<int> ballots[BALLOT_MAX_COUNT];
  25.  
  26. bool isCandidateAlive(int candidateId)
  27. {
  28.    return candidates[candidateId].second;
  29. };
  30.  
  31. void popUntilAliveCandidate(vector<int> &candidateIds)
  32. {
  33.    while (!candidateIds.empty())
  34.    {
  35.       int candidateId = candidateIds.front();
  36.       if (isCandidateAlive(candidateId))
  37.          break;
  38.       candidateIds.erase(candidateIds.begin());
  39.    }
  40. };
  41.  
  42. void initializeAliveCandidateBallots(candidateId *curBallots, int aliveCandidateCount)
  43. {
  44.    int id = 0;
  45.    for (int i = 0; i < aliveCandidateCount; ++i)
  46.    {
  47.       while (!isCandidateAlive(id))
  48.       {
  49.          id++;
  50.       }
  51.  
  52.       curBallots[i] = candidateId(id++, 0);
  53.    }
  54. };
  55.  
  56. candidateId *getCandidateId(int id, candidateId *curBallots, int aliveCandidateCount)
  57. {
  58.    for (int i = 0; i < aliveCandidateCount; ++i)
  59.       if (curBallots[i].first == id)
  60.          return curBallots + i;
  61. };
  62.  
  63. int main()
  64. {
  65.    //ifstream inputFile("input.txt");   // change to cin
  66.    //ofstream outputFile("output.txt");
  67.  
  68.    string input;
  69.    getline(cin, input);
  70.    int numTest = atoi(input.c_str());
  71.  
  72.    getline(cin, input);   // first blank line
  73.  
  74.    for (int k = 1; k <= numTest; k++)
  75.    {
  76.       memset(candidates, 0, sizeof(candidate) * CANDIDATE_MAX_COUNT);
  77.       for (int i = 0; i < BALLOT_MAX_COUNT; ++i)
  78.          ballots[i].clear();
  79.  
  80.       while (getline(cin, input))
  81.       {
  82.          if (!isStringEmptyOrWhitespace(input))
  83.             break;
  84.       }
  85.  
  86.       int candidateCount = atoi(input.c_str());
  87.  
  88.       for (int i = 0; i < candidateCount; ++i)
  89.       {
  90.          getline(cin, input);
  91.          candidates[i] = candidate(input, true);
  92.       }
  93.  
  94.       int ballotCount = 0;
  95.       while (getline(cin, input))
  96.       {
  97.          if (isStringEmptyOrWhitespace(input))
  98.             break;
  99.  
  100.          vector<string> ids;
  101.          tokenizeString(input, ids, " ");
  102.  
  103.          for (auto it = ids.begin(); it != ids.end(); it++)
  104.             ballots[ballotCount].push_back(atoi((*it).c_str()) - 1);
  105.  
  106.          ballotCount++;
  107.       }
  108.  
  109.       vector<int> winnerIds;
  110.       int aliveCandidateCount = candidateCount;
  111.  
  112.       if (ballotCount == 0)
  113.       {
  114.          for (int i = 0; i < aliveCandidateCount; ++i)
  115.             winnerIds.push_back(i);
  116.       }
  117.  
  118.       while (ballotCount > 0)
  119.       {
  120.          candidateId *curBallots = new candidateId[aliveCandidateCount];
  121.          initializeAliveCandidateBallots(curBallots, aliveCandidateCount);
  122.  
  123.          for (int i = 0; i < ballotCount; ++i)
  124.          {
  125.             getCandidateId(ballots[i].front(), curBallots, aliveCandidateCount)->second++;
  126.          }
  127.  
  128.          sort(curBallots, curBallots + aliveCandidateCount, candidateIdCompare);
  129.  
  130.          float voteRatio = (float)curBallots[aliveCandidateCount-1].second / ballotCount;
  131.          if (voteRatio > 50)
  132.          {
  133.             winnerIds.push_back(curBallots[aliveCandidateCount-1].first);
  134.             break;
  135.          }
  136.          else
  137.          {
  138.             bool isVoteRatioAllTheSame = true;
  139.             for (int i = 1; i < aliveCandidateCount; ++i)
  140.             {
  141.                if (curBallots[0].second != curBallots[i].second)
  142.                {
  143.                   isVoteRatioAllTheSame = false;
  144.                   break;
  145.                }
  146.             }
  147.  
  148.             if (isVoteRatioAllTheSame)
  149.             {
  150.                for (int i = 0; i < aliveCandidateCount; ++i)
  151.                {
  152.                   winnerIds.push_back(curBallots[i].first);
  153.                }
  154.                break;
  155.             }
  156.             else
  157.             {
  158.                int numVotes = curBallots[0].second;
  159.                int newlyDeadCandidateCount = 0;
  160.                for (int i = 0; i < aliveCandidateCount; ++i)
  161.                {
  162.                   if (curBallots[i].second == numVotes)
  163.                   {
  164.                      int deadId = curBallots[i].first;
  165.                      candidates[deadId].second = false;
  166.                      newlyDeadCandidateCount++;
  167.                   }
  168.                   else
  169.                   {
  170.                      break;
  171.                   }
  172.                }
  173.  
  174.                aliveCandidateCount -= newlyDeadCandidateCount;
  175.                for (int i = 0; i < ballotCount; ++i)
  176.                {
  177.                   popUntilAliveCandidate(ballots[i]);
  178.                }
  179.             }
  180.          }
  181.       }
  182.  
  183.       for (auto it = winnerIds.begin(); it != winnerIds.end(); ++it)
  184.       {
  185.          cout << candidates[(*it)].first << endl;
  186.       }
  187.  
  188.       if (k < numTest)
  189.          cout << endl;
  190.    }
  191.  
  192.    //inputFile.close();
  193.    //outputFile.close();
  194.  
  195.    return 0;
  196. }
  197.  
  198. void tokenizeString(const string &str, vector<string>& tokens, const string &delimiters = " ")
  199. {
  200.     // Skip delimiters at beginning.
  201.     string::size_type lastPos = str.find_first_not_of(delimiters, 0);
  202.     // Find first "non-delimiter".
  203.     string::size_type pos = str.find_first_of(delimiters, lastPos);
  204.  
  205.     while (pos != string::npos || lastPos != string::npos)
  206.     {
  207.         // Found a token, add it to the vector.
  208.         tokens.push_back(str.substr(lastPos, pos - lastPos));
  209.         // Skip delimiters.  Note the "not_of"
  210.         lastPos = str.find_first_not_of(delimiters, pos);
  211.         // Find next "non-delimiter"
  212.         pos = str.find_first_of(delimiters, lastPos);
  213.     }
  214. }
  215.  
  216. bool candidateIdCompare(const candidateId &c1, const candidateId &c2)
  217. {
  218.    return c1.second < c2.second;
  219. }
  220.  
  221. bool isStringEmptyOrWhitespace(string str)
  222. {
  223.    if (str.empty() || str.find_first_not_of(' ') == std::string::npos)
  224.       return true;
  225.    return false;
  226. }
Runtime error #stdin #stdout 0s 3448KB
comments (?)
stdin
copy 
1

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
stdout
copy 
Standard output is empty
https://ideone.com/ZVjq6e
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!