Submission #69855060

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
using ll = long long;
using db = double;
const ll N = 1e6 + 5;
const ll md = 998244353;
const ll MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db eps = 1e-6;
const db E = 2.718281828459045;
typedef pair<ll, ll> PLL;
#define fi first
#define se second
ll pre0[N], pre1[N], suf0[N], suf1[N];
void solve()
{
    ll n;
    cin >> n;
    string s;
    cin >> s;
    s = '#' + s;
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '0')
            pre0[i] = suf0[i] = 1;
        else
            pre1[i] = suf1[i] = 1;
    }
    suf1[n + 1] = suf0[n + 1] = 0;
    for (ll i = 1; i <= n; i++)
    {
        pre0[i] += pre0[i - 1];
        pre1[i] += pre1[i - 1];
    }
    for (ll i = n; i >= 1; i--)
    {
        suf0[i] += suf0[i + 1];
        suf1[i] += suf1[i + 1];
    }
    ll ans = 1e18;
    ll l = 0, r = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '1')
        {
            r = i;
            if (s[i] == '1' && l == 0)
                l = i;
        }
        else
        {
            // cout << l << ' ' << r << '\n';
            if (l != 0 && r != 0)
            {
                ll res0 = pre0[l - 1] + suf0[r + 1];
                ll res1 = 2 * (pre1[l - 1] + suf1[r + 1]);
                ans = min(res0 + res1, ans);
            }
            l = 0;
        }
    }
    if (l != 0 && r != 0)
    {
        ll res0 = pre0[l - 1] + suf0[r + 1];
        ll res1 = 2 * (pre1[l - 1] + suf1[r + 1]);
        ans = min(res0 + res1, ans);
    }
    l = 0, r = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '0')
        {
            r = i;
            if (s[i] == '0' && l == 0)
                l = i;
        }
        else
        {
            if (l != 0 && r != 0)
            {
                ll res0 = 2 * (pre0[l - 1] + suf0[r + 1]);
                ll res1 = (pre1[l - 1] + suf1[r + 1]);
                ans = min(res0 + res1, ans);
            }
            l = 0;
        }
    }
    if (l != 0 && r != 0)
    {
        ll res0 = 2 * (pre0[l - 1] + suf0[r + 1]);
        ll res1 = (pre1[l - 1] + suf1[r + 1]);
        ans = min(res0 + res1, ans);
    }
    for (ll i = 1; i <= n; i++)
        pre0[i] = pre1[i] = suf0[i] = suf1[i] = 0;
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Submission Info

Judge Result