結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2023-08-15 23:32:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 805 bytes |
コンパイル時間 | 595 ms |
コンパイル使用メモリ | 71,980 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-24 08:57:19 |
合計ジャッジ時間 | 6,934 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;using ll = long long;bool f(const vector<ll> &a, const vector<ll> &tot, int l, int r){if(r-l <= 0) return false;// cerr << l << " " << r << ", ";ll ave = tot[r]-tot[l];int ac = r, wa = l-1;while(ac-wa > 1){int wj = (ac+wa)/2;if(ave <= a[wj]*(r-l)) ac = wj;else wa = wj;}if(ac == l) return true;if(!f(a, tot, ac, r)) return true;if(!f(a, tot, l, ac)) return true;return false;}int main(){int n; cin >> n;vector<ll> a(n);for(auto &it: a) cin >> it;vector<ll> tot(n+1, 0);for(int i = 0; i < n; i++) tot[i+1] = tot[i]+a[i];cout << (f(a, tot, 0, n) ? "First" : "Second") << endl;return 0;}