結果
問題 | 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; }