D - Binary String Sorting.cpp

#ifdef DEBUG
#include "debug.h"
#endif // DEBUG
#ifndef DEBUG
template <typename T>
void debug(T &x){}
template <typename T>
void debug(T &x, int i, int j){}
#endif // DEBUG

#include <bits/stdc++.h>

using namespace std;

int n;
string s;
vector <int> sum;

long long int getCost(int k){
    long long int res = 0;

    if(k){
        res += sum[k - 1];
        res += (n - k) - (sum[n - 1] - sum[k - 1]);
    }else res = n - sum[n - 1];
    res *= 1e12 + 1;

    if(k && s[k - 1] == '1' && s[k] == '0') res -= 1e12 + 2;

    return res;
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        cin >> s;
        n = (int)s.size();
        for(char c : s){
            if(sum.empty()) sum.push_back(c - '0');
            else sum.push_back(sum.back() + c - '0');
        }

        long long int ans = LLONG_MAX;
        for(int i = 0; i <= n; i++) ans = min(ans, getCost(i));
        cout << ans << "\n";

        sum.clear();
    }
}