Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define all(x) x.begin(), x.end()
  6.  
  7. template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
  8. template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
  9.  
  10. int ans1 = 0, ans2 = 0, ans3 = 0;
  11.  
  12. void recalc(int a, int b, int c) {
  13. if (a + b + c <= ans1 + ans2 + ans3) return;
  14. if (a >= b || a >= c) return;
  15. ans1 = a, ans2 = b, ans3 = c;
  16. }
  17.  
  18. void solve() {
  19. int n;
  20. vector<int> a;
  21. cin >> n;
  22. int last;
  23. cin >> last;
  24. a.push_back(1);
  25. for (int i = 0; i < n - 1; i++) {
  26. int x;
  27. cin >> x;
  28. if (x == last)
  29. a[a.size() - 1]++;
  30. else
  31. a.push_back(1);
  32. last = x;
  33. }
  34. for (int i = 1; i < a.size(); i++)
  35. a[i] += a[i - 1];
  36. if (a.size() < 3) {
  37. cout << "0 0 0" << "\n";
  38. return;
  39. }
  40.  
  41. /* cout << "a = " << endl;
  42. for (auto i : a)
  43. cout << i << " ";
  44. cout << endl;*/
  45.  
  46.  
  47. int pos_gold = 0, pos_silver = 1, pos_bronze = 2;
  48. int cnt_medals = a[2];
  49. ans1 = 0, ans2 = 0, ans3 = 0;
  50. while (true) {
  51. int nxt_gold = a[pos_gold];
  52. int nxt_silver = a[pos_silver] - a[pos_gold];
  53. int nxt_bronze = a[pos_bronze] - a[pos_silver];
  54. recalc(nxt_gold, nxt_silver, nxt_bronze);
  55.  
  56. pos_bronze++;
  57. cnt_medals = a[pos_bronze];
  58. if (cnt_medals > n / 2) break;
  59. nxt_gold = a[pos_gold];
  60. nxt_silver = a[pos_silver] - a[pos_gold];
  61. nxt_bronze = a[pos_bronze] - a[pos_silver];
  62. recalc(nxt_gold, nxt_silver, nxt_bronze);
  63.  
  64. //cout << cnt_medals << " " << endl;
  65. while (pos_silver + 1 < pos_bronze) {
  66. int nxt_gold = a[pos_gold];
  67. int nxt_silver = a[pos_silver + 1] - a[pos_gold];
  68. int nxt_bronze = a[pos_bronze] - a[pos_silver + 1];
  69. //cout << "ansos = " << nxt_gold << " " << nxt_silver << " " << nxt_bronze << endl;
  70. recalc(nxt_gold, nxt_silver, nxt_bronze);
  71. if (nxt_gold >= nxt_silver) break;
  72. if (nxt_gold >= nxt_bronze) break;
  73. pos_silver++;
  74. }
  75.  
  76. while (pos_gold + 1 < pos_silver) {
  77. int nxt_gold = a[pos_gold + 1];
  78. int nxt_silver = a[pos_silver] - a[pos_gold + 1];
  79. int nxt_bronze = a[pos_bronze] - a[pos_silver];
  80. //cout << "ansos2 = " << nxt_gold << " " << nxt_silver << " " << nxt_bronze << endl;
  81. recalc(nxt_gold, nxt_silver, nxt_bronze);
  82. if (nxt_gold >= nxt_silver) break;
  83. if (nxt_gold >= nxt_bronze) break;
  84. pos_gold++;
  85. }
  86. }
  87. cout << ans1 << " " << ans2 << " " << ans3 << "\n";
  88. }
  89.  
  90. signed main() {
  91. ios_base::sync_with_stdio(0);
  92. cin.tie(0);
  93. cout.tie(0);
  94. int t;
  95. cin >> t;
  96. while (t--) {
  97. solve();
  98. }
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement