結果
問題 |
No.576 E869120 and Rings
|
ユーザー |
![]() |
提出日時 | 2025-04-20 17:30:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,007 bytes |
コンパイル時間 | 3,694 ms |
コンパイル使用メモリ | 278,484 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-20 17:30:33 |
合計ジャッジ時間 | 4,891 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:36:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | freopen("sapphire.in","r",stdin); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:37:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | freopen("sapphire.out","w",stdout); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; int n,k; string s; double pre[500005]; deque<int> q; bool check(double mid) { for(int j=0;j<=2*n;j++) pre[j]=0.0; for(int j=0;j<2*n;j++) { int val=(s[j]=='1')?1:0; pre[j+1]=pre[j]+(val-mid); } q.clear(); 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() { freopen("sapphire.in","r",stdin); freopen("sapphire.out","w",stdout); cin>>n>>k>>s; s+=s; double l=0.0,r=1.0; for(int _=1;_<=100;_++) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.15f",r); return 0; }