SHARE
TWEET

Untitled

a guest Feb 24th, 2020 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <deque>
  9. using namespace std;
  10.  
  11.  
  12. int main() {
  13.     string tests;
  14.     string line;
  15.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */
  16.     getline(cin, tests);
  17.     getline(cin, line);
  18.    // int counter = 0
  19.     for(int i = 0; i < std::stoi(tests); i++){
  20.         int p;
  21.         cin >> p;
  22.         getline(cin, line);
  23.         // cout << candidates;
  24.         vector<string> c(p);
  25.         // unordered_map<class vect, class _Tp>
  26.         for(int j = 0; j < p; j++){
  27.             getline(cin, c[j]);
  28.             // cout << c[j];
  29.             // cout << j;
  30.         }
  31.         string s;
  32.         deque<deque<int>> ballots;
  33.         while(std::getline(std::cin,s) && s[0] != 0){
  34.             deque<int> b;
  35.             // vector <string> votes;
  36.  
  37.             // split(votes, s, " ")
  38.             // for (int v = 0; v < votes.size(); v++){
  39.             //     cout << v << endl;
  40.             // }
  41.             for(int x = 0; x <= s.size(); x++){
  42.                 int vote = 0;
  43.                 while(s[x] != ' ' && s[x] != 0){
  44.                     vote = vote*10;
  45.                     vote = vote+(s[x]-48);
  46.                     ++x;
  47.                 }
  48.                 b.push_back(vote);
  49.                 // cout << s[x];
  50.             }
  51.             //cout << endl;
  52.             //cout << b.size();
  53.             ballots.push_back(b);
  54.             //cout << s << endl << s.size();
  55.         }
  56.         deque<deque<deque<int>>> candidates(p);
  57.         // cout << candidates.size() << endl;
  58.         for (int k = 0; k < ballots.size(); k++){
  59.             int top_vote = ballots[k][0];
  60.             // cout << endl << "topvote : "<< top_vote << endl;
  61.             // cout << ballots[k][0];
  62.             candidates[top_vote-1].push_back(ballots[k]);
  63.             // for(int q = 0; q < ballots[k].size(); q++){
  64.             //     cout << ballots[k][q] << " " ;
  65.             // }
  66.             // cout << endl;
  67.         }
  68.        
  69.         // for (int k = 0; k < candidates.size(); k++){
  70.         //     cout << candidates[k].size() << " ";
  71.         // }
  72.         // cout << endl << candidates.size() << endl;
  73.         // cout << ballots.size() << endl;
  74.         int tie_count = candidates[0].size();
  75.         int minimum = 1001;
  76.         bool tie = 0;
  77.         bool flag = 1;
  78.         int counternew = 0;
  79.         while (flag){
  80.             ++counternew;
  81.             // cout << endl<< "counter : " << counternew++<< endl;
  82.             tie_count = 0;
  83.             minimum = 1001;
  84.             tie = 0;            
  85.             for (int k = 0; k < candidates.size(); k++){
  86.                 // cout << candidates[k].size() << endl;
  87.                 if(candidates[k].size() != 0 && tie_count == 0)
  88.                     tie_count = candidates[k].size();
  89.                     // cout << tie_count <<endl;
  90.                 if (candidates[k].size() > ballots.size()/2){
  91.                     //cout << candida ballots.size()/2 << endl;
  92.                    
  93.                     // cout << endl << "candidate" << k << endl;
  94.                     // cout << endl << "Majority vote" << endl;
  95.                     if(i == std::stoi(tests)-1)
  96.                         cout << c[k];
  97.                     else
  98.                          cout << c[k] << endl;
  99.                     flag = 0;
  100.                     tie = 1;
  101.                     break;
  102.                 }    
  103.                 else {
  104.                     // cout << endl << "in else" << endl;
  105.                     if (candidates[k].size() != tie_count && candidates[k].size() != 0) {
  106.                         // cout << endl << "not TIE" << endl;
  107.                         tie = 1;
  108.                     }
  109.                     if (candidates[k].size() < minimum  && candidates[k].size() != 0)
  110.                         minimum = candidates[k].size();
  111.                     }
  112.             }
  113.             if (flag == 0)
  114.                 break;
  115.             if (tie == 0){
  116.                 flag = 1;
  117.                 break;
  118.             }
  119.             for (int k = 0; k < candidates.size(); k++){
  120.                 int size = candidates[k].size();
  121.                 if (size == minimum && size != 0){
  122.                     for(int b = 0; b < minimum; b++){
  123.                         candidates[k][b].pop_front();
  124.                         // cout << endl << "re-assigning ballot" << endl;
  125.                         int top_vote = candidates[k][b][0];
  126.                         while(candidates[top_vote - 1].size() == 0 || candidates[top_vote-1].size() == minimum){
  127.                                 candidates[k][b].pop_front();
  128.                                 top_vote = candidates[k][b][0];
  129.                         }
  130.                         candidates[top_vote-1].push_back(candidates[k][b]);
  131.                     }
  132.                     for(int b = 0; b < minimum; b++){
  133.                         candidates[k].pop_front(); }
  134.                 }
  135.             }
  136.         }
  137.         if (tie == 0){
  138.             for (int k = 0; k <candidates.size(); k++){
  139.                 if (candidates[k].size() != 0)
  140.                 {
  141.                     // cout << endl << "tie!" <<endl;
  142.                     cout << c[k]<<endl;
  143.                 }
  144.             }
  145.             }
  146.         if(i != std::stoi(tests)-1)
  147.            // cout<<counternew<<endl;
  148.             cout<<endl;
  149.         }
  150.            
  151.     return 0;
  152.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top