fork download
  1. #include <iostream>
  2. #include<vector>
  3. #include <boost/algorithm/string.hpp>
  4. #include <string>
  5. #include <map>
  6. #include <algorithm>
  7. using namespace std;
  8. using namespace boost;
  9.  
  10.  
  11. typedef pair<int, string> is;
  12. typedef pair<int,int>ii;
  13. typedef vector<ii>vp;
  14. typedef vector<int> v;
  15. typedef vector<v> vv;
  16. typedef vector<string> vs;
  17.  
  18. bool empate(vp b){
  19.  
  20. for(int i=0;i<b.size()-1;++i){
  21. if(b[i].first!=b[i+1].first){
  22. return false;
  23. }
  24. }
  25. return true;
  26. }
  27.  
  28. int main() {
  29.  
  30. int t,n;
  31. v num;
  32.  
  33. cin>>t;
  34.  
  35. for(int k=0;k<t;++k){
  36. string name,trash,ballot;
  37. vs ballots,ballot1;
  38. map<int,string> names;
  39. vp tally;
  40. vv ballots1;
  41.  
  42.  
  43. cin>>n;
  44. num.push_back(n);
  45. getline(cin,trash);
  46. for(int i=0;i<n;++i){
  47. getline(cin,name);
  48. names.insert(is (i,name));
  49. tally.push_back(make_pair(0,i));
  50. }
  51.  
  52.  
  53.  
  54. while(getline(cin,ballot)&&ballot!=""){
  55. split(ballot1,ballot,is_any_of(" "));
  56. v aux;
  57. for(int i=0;i<ballot1.size();i++){
  58. if(ballot1[i].size()==1){
  59. aux.push_back(ballot1[i][0]-48);
  60. }else{
  61. aux.push_back(((ballot1[i][0]-48)*10)+(ballot1[i][1]-48));
  62. }
  63. }
  64. ballots1.push_back(aux);
  65. }
  66.  
  67.  
  68. int pob=ballots1.size();
  69.  
  70. while(names.size()>1||!empate(tally)){
  71.  
  72. for(int i=0;i<tally.size();++i){
  73. tally[i].first=0;
  74. }
  75.  
  76. for(int i=0;i<ballots1.size();++i){
  77. for(int j=0;j<tally.size();++j){
  78. if(tally[j].second==ballots1[i][0]-1){
  79. tally[j].first++;
  80. break;
  81. }
  82. }
  83. }
  84.  
  85. sort(tally.begin(),tally.end());
  86.  
  87. if(empate(tally)){
  88. break;
  89. }
  90.  
  91. int max=tally[tally.size()-1].first;
  92.  
  93. if(max*10>=(pob*10)/2){
  94. cout<<names[tally[tally.size()-1].second]<<'\n';
  95. break;
  96.  
  97. }else{
  98. int min=tally[0].first;
  99.  
  100. v eliminate;
  101.  
  102. for(int i=0;i<tally.size();++i){
  103. if(tally[i].first==min){
  104. eliminate.push_back(tally[i].second);
  105. }
  106. }
  107.  
  108. for(int i=0;i<eliminate.size();++i){
  109. names.erase(eliminate[i]);
  110.  
  111. for(int j=0;j<ballots1.size();++j){
  112. std::vector<int>::iterator position = std::find(ballots1[j].begin(), ballots1[j].end(), eliminate[i]+1);
  113. ballots1[j].erase(position);
  114. }
  115.  
  116.  
  117. for(int j=0;j<tally.size();++j){
  118. if(tally[j].second==eliminate[i]){
  119. tally.erase(tally.begin()+j);
  120. }
  121. }
  122. }
  123.  
  124. }
  125.  
  126. }
  127.  
  128. if(empate(tally)){
  129. for (std::map<int,string>::iterator it=names.begin(); it!=names.end(); ++it)
  130. std::cout << it->second <<'\n';
  131. }
  132. cout<<'\n';
  133. }
  134.  
  135. return 0;
  136. }
Success #stdin #stdout 0s 15264KB
stdin
100

4
A
B
C
D
1 2 4 3
4 1 2 3
2 4 3 1
3 1 4 2
3 2 4 1
4 1 2 3
2 4 3 1

5
A
B
C
D
E
5 1 2 4 3
1 3 4 2 5
3 1 5 2 4
3 1 4 5 2
5 1 3 4 2

2
A
B
2 1
2 1
2 1
2 1
2 1

2
A
B
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2

3
A
B
C
2 1 3
2 1 3
1 2 3
2 3 1
1 2 3

2
A
B
2 1

3
A
B
C
3 2 1
2 1 3
3 2 1
1 2 3
2 3 1
2 3 1
2 1 3

4
A
B
C
D
4 1 2 3
3 2 1 4
2 3 4 1

1
A
1
1
1
1
1
1
1
1
1

3
A
B
C
1 2 3
2 3 1
1 3 2

5
A
B
C
D
E
4 2 1 5 3
3 5 1 4 2
2 3 1 5 4
5 2 1 4 3
5 1 4 2 3
2 4 5 3 1
1 5 3 4 2
4 5 1 2 3
2 3 1 4 5

2
A
B
1 2
1 2

4
A
B
C
D
4 1 3 2
3 1 4 2
4 2 1 3
1 4 3 2
2 3 4 1
3 2 4 1
1 2 4 3
1 4 2 3
3 1 4 2

2
A
B
2 1
2 1
1 2
1 2
2 1
1 2
2 1
2 1
1 2

4
A
B
C
D
2 4 1 3
3 2 4 1
1 2 4 3
2 3 1 4

1
A
1
1
1
1
1
1
1

3
A
B
C
1 3 2
2 1 3
2 3 1

3
A
B
C
3 1 2
1 3 2
1 3 2
2 3 1
2 1 3

5
A
B
C
D
E
1 2 5 3 4
4 2 5 3 1
5 4 1 2 3
3 2 1 5 4
4 5 2 3 1
3 1 4 5 2
3 1 2 5 4

3
A
B
C
3 2 1
2 1 3
2 1 3
3 2 1
1 3 2

3
A
B
C
2 3 1
3 1 2
2 3 1
2 1 3
1 3 2
3 1 2
3 2 1
3 2 1

3
A
B
C
1 2 3
3 2 1
3 1 2
3 2 1
3 2 1
1 2 3
3 2 1
1 3 2
2 1 3

1
A
1
1
1

3
A
B
C
2 3 1

4
A
B
C
D
2 4 3 1
2 3 1 4
1 4 2 3
3 4 2 1
4 2 3 1
3 4 2 1
3 2 1 4
3 1 2 4

2
A
B
1 2
2 1
1 2
1 2

4
A
B
C
D
4 3 2 1
3 2 4 1
4 3 1 2
1 2 4 3
2 1 4 3
2 3 4 1
1 2 3 4

4
A
B
C
D
2 3 1 4
4 1 3 2
2 3 4 1
3 2 1 4
3 2 1 4
3 2 4 1
4 3 1 2
4 1 3 2

2
A
B
1 2
2 1
2 1
1 2

4
A
B
C
D
1 2 3 4
1 3 2 4
3 1 4 2
4 3 1 2
4 3 2 1
4 3 2 1
4 1 3 2
3 4 2 1
3 2 4 1

5
A
B
C
D
E
2 5 3 4 1
4 2 5 3 1
4 5 1 3 2
4 5 3 1 2
3 2 4 5 1
2 1 4 3 5
1 3 2 4 5

3
A
B
C
3 2 1
3 1 2
1 2 3
1 2 3
2 1 3
2 1 3
1 2 3

5
A
B
C
D
E
4 1 2 3 5
2 4 1 5 3
3 5 2 1 4
3 2 5 4 1
2 3 1 5 4
3 5 1 4 2
1 5 4 3 2
2 1 3 4 5
3 5 1 4 2
2 3 1 5 4

1
A
1
1
1
1
1
1
1
1
1

5
A
B
C
D
E
1 3 5 4 2

5
A
B
C
D
E
4 1 5 3 2
5 1 4 3 2
1 2 4 3 5

2
A
B
1 2
1 2
2 1
2 1
1 2
2 1
1 2
1 2
2 1

1
A
1
1
1
1
1
1
1

2
A
B
2 1
1 2
1 2
1 2
1 2
2 1
2 1

2
A
B
2 1
1 2
1 2
2 1
1 2
2 1
2 1
2 1
1 2
2 1

3
A
B
C
3 1 2
2 3 1
3 2 1
2 1 3

3
A
B
C
1 3 2
1 2 3
1 3 2
1 2 3

4
A
B
C
D
3 1 4 2
1 3 4 2
4 2 3 1
2 1 3 4
3 2 1 4
1 4 2 3
1 4 2 3

4
A
B
C
D
2 3 1 4
2 3 1 4
1 4 3 2
4 1 2 3
2 1 4 3

2
A
B
1 2
1 2
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1

2
A
B
2 1
1 2
2 1
1 2

3
A
B
C
1 2 3
3 1 2
3 2 1
1 2 3

3
A
B
C
1 2 3
3 2 1
1 3 2
2 3 1
2 1 3
2 3 1
1 2 3
1 2 3

4
A
B
C
D
1 2 3 4
4 3 2 1

2
A
B
1 2
2 1
2 1
2 1

3
A
B
C
1 3 2
3 1 2
1 2 3
1 2 3

3
A
B
C
1 2 3
2 1 3
1 3 2
1 2 3
2 3 1
3 1 2
3 1 2
3 1 2
1 3 2

1
A
1
1
1
1
1
1
1
1
1

4
A
B
C
D
4 2 3 1

5
A
B
C
D
E
5 4 1 3 2
5 2 4 3 1
2 1 3 5 4
3 2 1 4 5
1 5 2 3 4
4 3 1 2 5
2 5 3 4 1

3
A
B
C
2 3 1
3 1 2
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
1 2 3
1 2 3

5
A
B
C
D
E
5 4 1 3 2
3 2 5 1 4
3 2 1 4 5

1
A
1

3
A
B
C
3 2 1
3 1 2
2 1 3
3 1 2
3 2 1
3 1 2
2 1 3

2
A
B
1 2
1 2
2 1
2 1
2 1
1 2
2 1
1 2
2 1

3
A
B
C
1 3 2
2 1 3
1 2 3
3 1 2
1 3 2
1 2 3
2 1 3
1 3 2
3 1 2
3 2 1

3
A
B
C
2 1 3
3 1 2
2 3 1
1 2 3
2 3 1
3 2 1
3 1 2
3 1 2
2 1 3

3
A
B
C
2 3 1

5
A
B
C
D
E
2 1 3 5 4
5 4 1 3 2
2 1 5 4 3
5 2 1 4 3
4 5 1 3 2

3
A
B
C
3 2 1
1 2 3
2 1 3

2
A
B
1 2
1 2
1 2

5
A
B
C
D
E
1 3 2 4 5
3 2 1 5 4
1 3 2 4 5
4 5 1 2 3
3 1 5 2 4
5 2 4 1 3
3 5 4 2 1
1 2 4 3 5
5 3 2 4 1

4
A
B
C
D
1 2 4 3
1 2 4 3
2 3 1 4
4 1 2 3
3 4 2 1

4
A
B
C
D
3 1 4 2
3 4 2 1
2 4 1 3
3 4 1 2

3
A
B
C
3 1 2
3 1 2
3 2 1
3 2 1
1 3 2
2 3 1
3 2 1
3 1 2

5
A
B
C
D
E
4 1 3 2 5
1 4 3 5 2
5 4 2 1 3
5 1 4 2 3
2 3 1 5 4

3
A
B
C
1 3 2
3 1 2
1 2 3
2 3 1
1 3 2
3 2 1
2 1 3

5
A
B
C
D
E
3 5 4 2 1
5 3 2 1 4
5 1 4 3 2
1 3 2 4 5

1
A
1

1
A
1
1
1
1
1
1
1
1
1

4
A
B
C
D
1 4 3 2
4 1 2 3

2
A
B
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2

3
A
B
C
3 2 1
3 1 2
1 2 3
1 3 2
2 3 1
3 1 2
1 2 3
3 2 1
1 3 2

4
A
B
C
D
3 2 1 4
4 2 1 3
1 2 4 3
3 2 4 1
4 3 2 1

2
A
B
2 1
1 2
1 2
1 2
2 1
1 2

5
A
B
C
D
E
3 1 5 2 4
5 4 3 1 2
4 3 2 5 1
1 3 2 5 4

5
A
B
C
D
E
2 5 1 3 4

1
A
1
1
1
1
1
1
1

5
A
B
C
D
E
4 3 1 5 2
3 4 5 2 1
3 2 1 4 5
2 5 4 1 3
2 5 1 4 3
2 1 5 3 4
3 1 5 4 2
3 2 4 1 5

2
A
B
2 1
2 1
1 2
1 2
2 1
2 1
2 1
2 1
2 1
2 1

4
A
B
C
D
3 1 4 2
1 4 2 3

1
A
1
1
1
1
1
1

2
A
B
1 2
1 2
2 1
1 2
1 2
2 1
1 2

1
A
1
1
1
1
1

2
A
B
1 2
1 2
1 2
2 1
2 1
2 1
2 1
2 1
1 2
1 2

1
A
1
1
1
1
1
1
1
1
1

5
A
B
C
D
E
4 2 1 5 3
4 1 3 2 5
1 5 2 3 4

1
A
1
1
1
1
1
1

4
A
B
C
D
2 1 3 4
1 2 4 3
3 1 4 2
4 1 2 3
4 3 1 2
2 1 3 4
1 3 2 4
1 4 3 2
4 1 2 3
3 4 2 1

1
A
1
1
1
1
1
1

2
A
B
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1

5
A
B
C
D
E
4 1 2 3 5
4 5 1 2 3
3 4 2 1 5
5 1 4 3 2

2
A
B
2 1
2 1
2 1
2 1
1 2
2 1
1 2
1 2
2 1
1 2

1
A
1
1

1
A
1
1
stdout
B

C

B

A

B

B

B

B
C
D

A

A

E

A

A

B

B

A

B

A

C

C

C

C

A

B

C

A

B

C

A
B

C

B

A

B
C

A

A

A
D
E

A

A

A

B

C

A

A

B

A

A
B

C

A

D

B

A

A

A

D

B

A
B
C

C

A

C

B

A

B

B

E

A
B
C

A

A
C
E

A

C

C

E

A

E

A

A

D

A

C

D

A

A
C
D
E

B

A

C

B

C

A

A

A

A
B

A

D

A

A

A

A

D

B

A

A