結果

問題 No.576 E869120 and Rings
ユーザー vjudge1
提出日時 2025-04-18 17:24:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,230 ms / 1,500 ms
コード長 965 bytes
コンパイル時間 3,516 ms
コンパイル使用メモリ 281,440 KB
実行使用メモリ 13,128 KB
最終ジャッジ日時 2025-04-18 17:25:21
合計ジャッジ時間 24,143 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int n,k;string s;
bool check(double mid){
    vector<double>pre(2*n+1,0.0);
    for(int j=0;j<2*n;j++){
        int val=(s[j]=='1')?1:0;
        pre[j+1]=pre[j]+(val-mid);
    }deque<int>q;
    for(int j=0;j<2*n;j++){
        int now=j+1,ima=now-k;
        if(ima>=0){
            while(!q.empty()&&pre[q.back()]>=pre[ima])q.pop_back();
            q.push_back(ima);
        }int imi=now-n;
        if(imi<0)imi=0;
        while(!q.empty()&&q.front()<imi)q.pop_front();
        if(now>=k){
            if(!q.empty()){
                if(pre[now]-pre[q.front()]>=-1e-9)return 1;
            }
        }
    }
    return 0;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>k>>s;s=s+s;
    double low=0.0,high=1.0;
    for (int i=0;i<100;i++){
        double mid=(low+high)/2;
        if(check(mid))low = mid;
        else high=mid;
    }
    printf("%.15lf",high);
    return 0;
}
0