結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2019-01-18 13:35:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,315 bytes |
コンパイル時間 | 1,113 ms |
コンパイル使用メモリ | 111,572 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 21:32:55 |
合計ジャッジ時間 | 5,742 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cfloat>#include <map>#include <utility>#include <set>#include <iostream>#include <memory>#include <string>#include <vector>#include <algorithm>#include <functional>#include <sstream>#include <complex>#include <stack>#include <queue>#include <iomanip>#include <array>#include <numeric>#include <regex>#include <bitset>#include <deque>#include <cassert>using namespace std;typedef long long ll;typedef pair<int, int> p_ii;const int INF = 1e9;const double PI = acos(-1.0);const ll MOD = 1e9 + 7;#define sz(x) ((int)(x).size())#define all(x) (x).begin(), (x).end()#define debug(x) cout << #x << ": " << x << endl;#define popcnt __builtin_popcountint N;vector<ll> a(100010), cum(100010, 0);int dfs(int L, int R){ //範囲(L, R]からの勝敗if(L>=R) return 0;ll sum = cum[R]-cum[L];int ok = L, ng = R;//範囲(L, R]での境界while(ng-ok>1){int mid = (ok+ng)/2;if(a[mid]*(R-L)<sum)ok=mid;else ng=mid;}return !dfs(L, ok) || !dfs(ok, R);}int main() {cin>>N;for (int i = 1; i <= N; i++) cin>>a[i];for (int i = 1; i < N+1; i++) cum[i]=cum[i-1]+a[i];if(dfs(0, N))puts("First");else puts("Second");return 0;}