結果

問題 No.1437 01 Sort
コンテスト
ユーザー novaandcabral
提出日時 2024-04-22 14:36:13
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,161 bytes
コンパイル時間 3,586 ms
コンパイル使用メモリ 130,804 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-10-14 13:42:24
合計ジャッジ時間 5,027 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 4 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long 
using namespace std;

// Function to count occurrences of '0' in string s
int count_zeros(const string& s) {
    int zeros = 0;
    for(char c : s) {
        if(c == '0')
            zeros++;
    }
    return zeros;
}

// Function to find the minimum between two integers
int min(int a, int b) {
    return (a < b) ? a : b;
}

signed main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unsigned long long ans = 1e10;

    int zero = count_zeros(s);
    int one = n - zero;
    if(zero == 0 || zero == n) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> out(n, 0);
    if(s[0] == '1') {
        out[0] = 1;
        for(int i = n-1; i >= 0; i--) {
            if(s[i] == '1')
                out[i] = 1;
            else
                break;
        }
    }

    vector<int> bit;
    for(int i = 0; i < n; i++) {
        if(s[i] == '1') {
            bit.push_back(i);
            bit.push_back(i+n);
            bit.push_back(i+n+n);
            bit.push_back(i+n+n+n);
        }
    }
    sort(bit.begin(), bit.end());

    auto f = [&](int l, int ll) {
        int sp_l = (l+one) % n;
        int sp_r = n;
        if(sp_l == 0)
            sp_l = n;

        int ansl = 0;
        if(bit[ll] <= l + n) {
            if(sp_l <= ((bit[ll]-1)%n + 1) && ((bit[ll]-1)%n + 1) <= sp_r && out[bit[ll] % n] == 0)
                ansl = l + n - bit[ll] - 1;
            else
                ansl = l + n - bit[ll];
        }

        int ansr = 0;
        if(l + n + one - 1 < bit[ll + one - 1]) {
            int ng = -1;
            int ok = one;
            while(ng + 1 != ok) {
                int mid = (ng + ok) / 2;
                if(l + n + mid < bit[ll + mid])
                    ok = mid;
                else
                    ng = mid;
            }

            bool flag1 = true;
            bool flag2 = false;
            int x = l + n + ok;
            if(x % n != 0)
                x += n - (x % n);
            if(x <= l + n + one - 1) {
                if(l + n + ok <= bit[ll + ok] && bit[ll + ok] <= x)
                    flag2 = true;
                x += n;
            }
            if(l + n + ok <= bit[ll + ok] && bit[ll + ok] <= x)
                flag1 = false;
            ansr = one - ok + flag1 - flag2;
        }
        return max(ansl, ansr);
    };

    for(int l = 0; l < n; l++) {
        int anss = (-l - one) % n;
        int sp_l = (l + one) % n;
        int sp_r = n;
        if(sp_l == 0)
            sp_l = n;

        int ng = -1;
        int ok = n;
        while(ng + 1 != ok) {
            int mid = (ng + ok) / 2;
            int x = l + n - mid - 1;
            if(!(sp_l <= ((x-1)%n + 1) && ((x-1)%n + 1) <= sp_r && out[x % n] == 0))
                x += 1;
            int ll = lower_bound(bit.begin(), bit.end(), x) - bit.begin();
            if(f(l, ll) <= mid)
                ok = mid;
            else
                ng = mid;
        }
        ans = min(ans, (unsigned long long)anss + (unsigned long long)ok * (unsigned long long)n);
    }

    cout << ans << endl;

    return 0;
}
0