結果

問題 No.761 平均値ゲーム
ユーザー iicafiaxus
提出日時 2018-12-09 03:27:49
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 1,007 bytes
コンパイル時間 826 ms
コンパイル使用メモリ 127,404 KB
実行使用メモリ 8,628 KB
最終ジャッジ日時 2024-06-13 02:06:54
合計ジャッジ時間 5,133 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

int n;
long[] as;
long[] sums; // sums[i] は as[i -1] までの和
void main(){
	n = read.to!int;
	as = readln.chomp.split.map!(to!long).array;
	
	sums = [0];
	foreach(a; as) sums ~= sums[$ - 1] + a;
	
	solve(0, n - 1).writeln;
}

string solve(int l, int r){ // [l, r]
	int c = uplimit(l, r, (int i) => as[i] * (r + 1 - l) < sums[r + 1] - sums[l]);
	if(c < l) return "First";
	else if(solve(l, c) == "Second") return "First";
	else if(solve(c + 1, r) == "Second") return "First";
	else return "Second";
}

// fをみたす最大
int uplimit(int a, int c, bool delegate(int) f){
	if(f(c)) return c;
	if(! f(a)) return a - 1;
	while(a + 1 < c){
		int b = (a + c) / 2;
		if(f(b)) a = b;
		else c = b;
	}
	return a;
}
0