結果

問題 No.1437 01 Sort
コンテスト
ユーザー vjudge1
提出日時 2024-08-09 12:23:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 344 ms / 2,000 ms
コード長 2,251 bytes
コンパイル時間 2,435 ms
コンパイル使用メモリ 187,436 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-09 12:23:40
合計ジャッジ時間 7,692 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NR=2e5+10;
int n,ans=1e18,cnt0,cnt1,out[NR];
string s;
vector<int>idx;
#define pb emplace_back

int calc(int l1,int l2){
    int L=(l1+cnt1)%n,R=n;
    if(!L)L=n;
    int ansl=0,ansr=0;
    if(idx[l2]<=l1+n){
        if(L<=(idx[l2]+n-1)%n+1&&(idx[l2]+n-1)%n+1<=R&&out[idx[l2]%n])ansl=l1+n-idx[l2]-1;
        else ansl=l1+n-idx[l2];
//       printf("bit[l2]:%lld ansl:%lld %lld %lld %lld\n",bit[l2],ansl,sp_l<=(bit[l2]+n-1)%n+1,sp_l,(bit[l2]+n-1)%n+1);
    }
//	cout<<l1<<" "<<l2<<" "<<ansl<<" "<<ansr<<endl; 
    if(l1+n+cnt1-1<idx[l2+cnt1-1]){
        int l=-1,r=cnt1;
        while(l+1!=r){
            int mid=(l+r)/2;
            if(l1+n+mid<idx[l2+mid])r=mid;
            else l=mid;
        }
        bool flag1=1,flag2=0;
        int x=l1+n+r;
        if(x%n)x+=n-(x%n);
        if(x<=l1+n+cnt1-1){
            if(l1+n+r<=idx[l2+r]&&idx[l2+r]<=x)flag2=1;
            x+=n;
        }
        if(l1+n+r<=idx[l2+r]&&idx[l2+r]<=x)flag1=0;
        ansr=cnt1-r;
        ansr+=flag1;
        ansr-=flag2;
    }
//	cout<<l1<<" "<<l2<<" "<<max(ansl,ansr)<<endl; 
    return max(ansl,ansr);
}

signed main(){
//	freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	cin>>n>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='0')cnt0++;
        else{
            cnt1++;
            idx.pb(i);idx.pb(i+n);idx.pb(i+n+n);
        }
    }
    sort(idx.begin(),idx.end());
    if(cnt0==n||cnt0==0){
    	cout<<0<<endl;
        return 0;
    }
	for(int i=0;i<n;i++)out[i]=1;
    if(s[0]=='1'){
        out[0]=0;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='1')out[i]=0;
            else break;
        }
    }
    for(int l1=0;l1<n;l1++){
        int res=(n+n-l1-cnt1)%n;
		int L=(l1+cnt1)%n,R=n;
        if(!L)L=n;
        int l=-1,r=n;
        while(l+1!=r){
            int mid=(l+r)/2;
            int x=l1+n-mid-1;
            if(!(L<=(x+n-1)%n+1&&(x+n-1)%n+1<=R&&out[x%n]))x++;
            int l2=lower_bound(idx.begin(),idx.end(),x)-idx.begin();
            if(calc(l1,l2)<=mid)r=mid;
            else l=mid;
        }
        ans=min(ans,res+r*n);
    }
    cout<<ans<<endl;
    return 0;
}
0