Submission #64328743

---

Source Code Expand

#include <bits/stdc++.h>
using ll = long long;

const int N = 3e5;

void solve() {
    ll n;
    std::cin >> n;
    std::vector<ll> a(2 * n + 10, 0);
    for (int i = 1; i <= 2 * n; i++) {
        std::cin >> a[i];
    }
    int cnt = 0;
    std::vector<ll> b;
    for (int i = 1; i <= 2 * n; i++) {
        if (a[i] != a[i - 1] && a[i] != a[i + 1]) {
            cnt++;
        } else if (cnt != 0) {
            b.push_back(cnt);
            cnt = 0;
        }
    }
    if (cnt != 0) {
        b.push_back(cnt);
    } else if (cnt == 0 && b.empty()) {
        std::cout << 0 << "\n";
        return;
    }
    if (b.size() == 1) {
        std::cout << n - 1 << "\n";
        return;
    }
    std::sort(b.begin(), b.end());
    int ans = 0;
    int m = b.size();
    for (int i = 0; i < m; i += 2) {
        if (b[i] % 2 == 0) {
            ans += b[i] / 2;
        } else {
            ans += b[i];
        }
    }
    std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false), std::cout.tie(nullptr), std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result