結果

問題 No.761 平均値ゲーム
ユーザー nebukuro09
提出日時 2018-12-09 00:42:57
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,001 bytes
コンパイル時間 1,104 ms
コンパイル使用メモリ 117,752 KB
実行使用メモリ 7,836 KB
最終ジャッジ日時 2024-06-13 02:06:25
合計ジャッジ時間 6,627 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;
    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    bool solve(bool t, int l, int r) {
        if (r == l)
            return t;
        if (A[l] == A[r])
            return t;

        long a = B[r+1] - B[l];
        int hi = r;
        int lo = l - 1;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            if (A[mid] * (r - l + 1) >= a) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        if (!t)
            return !(!solve(t^1, l, hi-1) || !solve(t^1, hi, r));
        else
            return solve(t^1, l, hi-1) || solve(t^1, hi, r);
    }

    writeln(solve(0, 0, N-1) ? "Second" : "First");
}
0