Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define all(x) x.begin(), x.end()
- template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
- template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
- int ans1 = 0, ans2 = 0, ans3 = 0;
- void recalc(int a, int b, int c) {
- if (a + b + c <= ans1 + ans2 + ans3) return;
- if (a >= b || a >= c) return;
- ans1 = a, ans2 = b, ans3 = c;
- }
- void solve() {
- int n;
- vector<int> a;
- cin >> n;
- int last;
- cin >> last;
- a.push_back(1);
- for (int i = 0; i < n - 1; i++) {
- int x;
- cin >> x;
- if (x == last)
- a[a.size() - 1]++;
- else
- a.push_back(1);
- last = x;
- }
- for (int i = 1; i < a.size(); i++)
- a[i] += a[i - 1];
- if (a.size() < 3) {
- cout << "0 0 0" << "\n";
- return;
- }
- /* cout << "a = " << endl;
- for (auto i : a)
- cout << i << " ";
- cout << endl;*/
- int pos_gold = 0, pos_silver = 1, pos_bronze = 2;
- int cnt_medals = a[2];
- ans1 = 0, ans2 = 0, ans3 = 0;
- while (true) {
- int nxt_gold = a[pos_gold];
- int nxt_silver = a[pos_silver] - a[pos_gold];
- int nxt_bronze = a[pos_bronze] - a[pos_silver];
- recalc(nxt_gold, nxt_silver, nxt_bronze);
- pos_bronze++;
- cnt_medals = a[pos_bronze];
- if (cnt_medals > n / 2) break;
- nxt_gold = a[pos_gold];
- nxt_silver = a[pos_silver] - a[pos_gold];
- nxt_bronze = a[pos_bronze] - a[pos_silver];
- recalc(nxt_gold, nxt_silver, nxt_bronze);
- //cout << cnt_medals << " " << endl;
- while (pos_silver + 1 < pos_bronze) {
- int nxt_gold = a[pos_gold];
- int nxt_silver = a[pos_silver + 1] - a[pos_gold];
- int nxt_bronze = a[pos_bronze] - a[pos_silver + 1];
- //cout << "ansos = " << nxt_gold << " " << nxt_silver << " " << nxt_bronze << endl;
- recalc(nxt_gold, nxt_silver, nxt_bronze);
- if (nxt_gold >= nxt_silver) break;
- if (nxt_gold >= nxt_bronze) break;
- pos_silver++;
- }
- while (pos_gold + 1 < pos_silver) {
- int nxt_gold = a[pos_gold + 1];
- int nxt_silver = a[pos_silver] - a[pos_gold + 1];
- int nxt_bronze = a[pos_bronze] - a[pos_silver];
- //cout << "ansos2 = " << nxt_gold << " " << nxt_silver << " " << nxt_bronze << endl;
- recalc(nxt_gold, nxt_silver, nxt_bronze);
- if (nxt_gold >= nxt_silver) break;
- if (nxt_gold >= nxt_bronze) break;
- pos_gold++;
- }
- }
- cout << ans1 << " " << ans2 << " " << ans3 << "\n";
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin >> t;
- while (t--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement