結果
問題 | No.576 E869120 and Rings |
ユーザー |
![]() |
提出日時 | 2017-10-13 23:59:32 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 1,300 ms / 1,500 ms |
コード長 | 13,804 bytes |
コンパイル時間 | 2,417 ms |
コンパイル使用メモリ | 154,376 KB |
実行使用メモリ | 54,576 KB |
最終ジャッジ日時 | 2024-06-12 22:01:39 |
合計ジャッジ時間 | 26,543 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
/+ dub.sdl:name "A"dependency "dcomp" version=">=0.7.3"+/import std.stdio, std.algorithm, std.range, std.conv;// import dcomp.foundation, dcomp.scanner;// import dcomp.algorithm;// import dcomp.container.deque;int main() {Scanner sc = new Scanner(stdin);int n, k;sc.read(n, k);string s;sc.read(s);s ~= s;bool pred(double md) {double[] sm = new double[2*n+1]; sm[] = 0;foreach (i; 0..2*n) {sm[i+1] = sm[i] + s[i] - '0' - md;}import std.container.rbtree;// auto tr = redBlackTree!(true, double);auto tr = Deque!int();int l = 0, r = 0;foreach (i; n..2*n+1) {//[i-n, i-k]while (r <= i-k) {while (tr.length && sm[tr.back] >= sm[r]) tr.removeBack;tr.insertBack(r);// tr.insert(sm[r]);r++;}while (l < i-n) {if (tr.length && tr.front == i) tr.removeFront;// tr.removeKey(sm[l]);l++;}if (sm[tr.front] <= sm[i]) return false;}return true;}writefln("%.20f", binSearch!(md => pred(md))(0.0, 1.0, 50));return 0;}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */// module dcomp.foundation;static if (__VERSION__ <= 2070) {/*Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.dCopyright: Andrei Alexandrescu 2008-.License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).*/template fold(fun...) if (fun.length >= 1) {auto fold(R, S...)(R r, S seed) {import std.algorithm : reduce;static if (S.length < 2) {return reduce!fun(seed, r);} else {import std.typecons : tuple;return reduce!fun(tuple(seed), r);}}}}version (X86) static if (__VERSION__ < 2071) {import core.bitop : bsf, bsr, popcnt;int bsf(ulong v) {foreach (i; 0..64) {if (v & (1UL << i)) return i;}return -1;}int bsr(ulong v) {foreach_reverse (i; 0..64) {if (v & (1UL << i)) return i;}return -1;}int popcnt(ulong v) {int c = 0;foreach (i; 0..64) {if (v & (1UL << i)) c++;}return c;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */// module dcomp.container.deque;struct DequePayload(T) {import core.exception : RangeError;import core.memory : GC;import std.range : ElementType, isInputRange;import std.traits : isImplicitlyConvertible;T *d;size_t st, length, cap;@property bool empty() const { return length == 0; }alias opDollar = length;ref inout(T) opIndex(size_t i) inout {version(assert) if (length <= i) throw new RangeError();return d[(st+i >= cap) ? (st+i-cap) : st+i];}private void expand() {import std.algorithm : max;assert(length == cap);auto nc = max(size_t(4), 2*cap);T* nd = cast(T*)GC.malloc(nc * T.sizeof);foreach (i; 0..length) {nd[i] = this[i];}d = nd; st = 0; cap = nc;}void clear() {st = length = 0;}void insertFront(T v) {if (length == cap) expand();if (st == 0) st += cap;st--; length++;this[0] = v;}void insertBack(T v) {if (length == cap) expand();length++;this[length-1] = v;}void removeFront() {assert(!empty, "Deque.removeFront: Deque is empty");st++; length--;if (st == cap) st = 0;}void removeBack() {assert(!empty, "Deque.removeBack: Deque is empty");length--;}ref inout(T) front() inout { return this[0]; }ref inout(T) back() inout { return this[$-1]; }Range opSlice() {return Range(&this, 0, length); }alias Range = RangeT!(DequePayload!T);alias ConstRange = RangeT!(const DequePayload!T);alias ImmutableRange = RangeT!(immutable DequePayload!T);static struct RangeT(A) {import std.traits : CopyTypeQualifiers;alias E = CopyTypeQualifiers!(A, T);A *p;size_t a, b;@property bool empty() const { return b <= a; }@property size_t length() const { return b-a; }@property RangeT save() { return RangeT(p, a, b); }@property RangeT!(const A) save() const {return typeof(return)(p, a, b);}alias opDollar = length;@property ref inout(E) front() inout { return (*p)[a]; }@property ref inout(E) back() inout { return (*p)[b-1]; }void popFront() {version(assert) if (empty) throw new RangeError();a++;}void popBack() {version(assert) if (empty) throw new RangeError();b--;}ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }RangeT opSlice() { return this.save; }RangeT opSlice(size_t i, size_t j) {version(assert) if (i > j || a + j > b) throw new RangeError();return typeof(return)(p, a+i, a+j);}RangeT!(const A) opSlice() const { return this.save; }RangeT!(const A) opSlice(size_t i, size_t j) const {version(assert) if (i > j || a + j > b) throw new RangeError();return typeof(return)(p, a+i, a+j);}}}struct Deque(T, bool mayNull = true) {import core.exception : RangeError;import core.memory : GC;import std.range : ElementType, isInputRange;import std.traits : isImplicitlyConvertible;alias Payload = DequePayload!T;alias Range = Payload.Range;alias ConstRange = Payload.ConstRange;alias ImmutableRange = Payload.ImmutableRange;Payload* p;private void I() { if (mayNull && !p) p = new Payload(); }private void C() const {version(assert) if (mayNull && !p) throw new RangeError();}static if (!mayNull) {@disable this();}private this(Payload* p) {this.p = p;}this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {p = new Payload();foreach (v; values) {insertBack(v);}}this(Range)(Range r)if (isInputRange!Range &&isImplicitlyConvertible!(ElementType!Range, T) &&!is(Range == T[])) {p = new Payload();foreach (v; r) {insertBack(v);}}static Deque make() { return Deque(new Payload()); }@property bool havePayload() const { return (!mayNull || p); }@property bool empty() const { return (!havePayload || p.empty); }@property size_t length() const { return (havePayload ? p.length : 0); }alias opDollar = length;ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; }ref inout(T) front() inout {C; return (*p)[0]; }ref inout(T) back() inout {C; return (*p)[$-1]; }void clear() { if (p) p.clear(); }void insertFront(T v) {I; p.insertFront(v); }void insertBack(T v) {I; p.insertBack(v); }alias stableInsertBack = insertBack;void removeFront() {C; p.removeFront(); }void removeBack() {C; p.removeBack(); }Range opSlice() {I; return Range(p, 0, length); }}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/algorithm.d */// module dcomp.algorithm;import std.range.primitives;import std.traits : isFloatingPoint, isIntegral;T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {while (r-l > 1) {T md = (l+r)/2;if (!pred(md)) l = md;else r = md;}return r;}T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {foreach (i; 0..cnt) {T md = (l+r)/2;if (!pred(md)) l = md;else r = md;}return r;}E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)if (isInputRange!Range && !isInfinite!Range) {import std.algorithm, std.functional;return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);}ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {assert(!range.empty, "range must not empty");auto e = range.front; range.popFront;return minimum!pred(range, e);}E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)if (isInputRange!Range && !isInfinite!Range) {import std.algorithm, std.functional;return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);}ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {assert(!range.empty, "range must not empty");auto e = range.front; range.popFront;return maximum!pred(range, e);}Rotator!Range rotator(Range)(Range r) {return Rotator!Range(r);}struct Rotator(Range)if (isForwardRange!Range && hasLength!Range) {size_t cnt;Range start, now;this(Range r) {cnt = 0;start = r.save;now = r.save;}this(this) {start = start.save;now = now.save;}@property bool empty() {return now.empty;}@property auto front() {assert(!now.empty);import std.range : take, chain;return chain(now, start.take(cnt));}@property Rotator!Range save() {return this;}void popFront() {cnt++;now.popFront;}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */// module dcomp.scanner;// import dcomp.array;class Scanner {import std.stdio : File;import std.conv : to;import std.range : front, popFront, array, ElementType;import std.array : split;import std.traits : isSomeChar, isStaticArray, isArray;import std.algorithm : map;File f;this(File f) {this.f = f;}char[512] lineBuf;char[] line;private bool succW() {import std.range.primitives : empty, front, popFront;import std.ascii : isWhite;while (!line.empty && line.front.isWhite) {line.popFront;}return !line.empty;}private bool succ() {import std.range.primitives : empty, front, popFront;import std.ascii : isWhite;while (true) {while (!line.empty && line.front.isWhite) {line.popFront;}if (!line.empty) break;line = lineBuf[];f.readln(line);if (!line.length) return false;}return true;}private bool readSingle(T)(ref T x) {import std.algorithm : findSplitBefore;import std.string : strip;import std.conv : parse;if (!succ()) return false;static if (isArray!T) {alias E = ElementType!T;static if (isSomeChar!E) {auto r = line.findSplitBefore(" ");x = r[0].strip.dup;line = r[1];} else static if (isStaticArray!T) {foreach (i; 0..T.length) {bool f = succW();assert(f);x[i] = line.parse!E;}} else {FastAppender!(E[]) buf;while (succW()) {buf ~= line.parse!E;}x = buf.data;}} else {x = line.parse!T;}return true;}int read(T, Args...)(ref T x, auto ref Args args) {if (!readSingle(x)) return 0;static if (args.length == 0) {return 1;} else {return 1 + read(args);}}}/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */// module dcomp.array;T[N] fixed(T, size_t N)(T[N] a) {return a;}struct FastAppender(A, size_t MIN = 4) {import std.algorithm : max;import std.conv;import std.range.primitives : ElementEncodingType;import core.stdc.string : memcpy;private alias T = ElementEncodingType!A;private T* _data;private uint len, cap;@property size_t length() const {return len;}bool empty() const { return len == 0; }void reserve(size_t nlen) {import core.memory : GC;if (nlen <= cap) return;void* nx = GC.malloc(nlen * T.sizeof);cap = nlen.to!uint;if (len) memcpy(nx, _data, len * T.sizeof);_data = cast(T*)(nx);}void free() {import core.memory : GC;GC.free(_data);}void opOpAssign(string op : "~")(T item) {if (len == cap) {reserve(max(MIN, cap*2));}_data[len++] = item;}void insertBack(T item) {this ~= item;}void removeBack() {len--;}void clear() {len = 0;}ref inout(T) back() inout { assert(len); return _data[len-1]; }ref inout(T) opIndex(size_t i) inout { return _data[i]; }T[] data() {return (_data) ? _data[0..len] : null;}}/*This source code generated by dcomp and include dcomp's source code.dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)*/