結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2018-12-09 00:20:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 663 bytes |
コンパイル時間 | 651 ms |
コンパイル使用メモリ | 59,384 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 18:16:01 |
合計ジャッジ時間 | 4,456 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <stdio.h>#include <algorithm>#include <map>using namespace std;map<pair<int, int>, bool> chk;long long A[100100],S[100100]; int N;bool go(int i, int j){if (i > j) return false;if (i == j) return true;if (chk.count({i,j})) return chk[{i,j}];long long u = (S[j+1] - S[i] - 1) / (j + 1 - i);long long v = (S[j+1] - S[i] + j - i) / (j + 1 - i);int p = upper_bound(A, A+N, u) - A;int q = lower_bound(A, A+N, v) - A - 1;return chk[{i,j}] = ((i < p && !go(p, j)) || !go(i, q));}int main(){scanf ("%d",&N);for (int i=0;i<N;i++){scanf ("%lld",&A[i]);S[i+1] = S[i] + A[i];}puts(go(0,N-1)?"First":"Second");return 0;}