結果
問題 |
No.576 E869120 and Rings
|
ユーザー |
![]() |
提出日時 | 2025-04-20 22:38:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,204 bytes |
コンパイル時間 | 3,613 ms |
コンパイル使用メモリ | 283,164 KB |
実行使用メモリ | 13,172 KB |
最終ジャッジ日時 | 2025-04-20 22:38:49 |
合計ジャッジ時間 | 33,554 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 TLE * 8 |
ソースコード
#include <bits/stdc++.h> //#define int long long //#define USE_FREOPEN //#define MUL_TEST #define FILENAME "sapphire" using namespace std; //constexpr double eps = 1e-6; int n,k; string s; bool chk(double x) { vector<double> sa(2 * n + 1,0.0); for (int i = 0; i < 2 * n; i++) { int val = (s[i] == '1') ? 1 : 0; sa[i + 1] = sa[i] + (val - x); } deque<int> q; for (int i = 1; i <= 2 * n; i++) { int imk = i - k,imn = max(i - n,0); if (imk >= 0) { while (q.size() && sa[q.back()] >= sa[imk]) q.pop_back(); q.push_back(imk); } while (q.size() && q.front() < imn) q.pop_front(); if (i >= k) { if (q.size()) { if (sa[i] - sa[q.front()] >= -1e-9) return 1; } } } return 0; } void solve() { cin >> n >> k >> s; s = s + s; double l = 0.0,r = 1.0; for (int i = 0; i < 100; i++) { double mid = (l + r) / 2.0; if (chk(mid)) l = mid; else r = mid; } printf("%.15lf\n",r); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef USE_FREOPEN freopen(FILENAME ".in","r",stdin); freopen(FILENAME ".out","w",stdout); #endif int _ = 1; #ifdef MUL_TEST cin >> _; #endif while (_--) solve(); _^=_; return 0^_^0; }