結果

問題 No.576 E869120 and Rings
ユーザー yosupot
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/+ 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.d
Copyright: 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)
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0