結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2018-12-09 00:11:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 929 bytes |
コンパイル時間 | 2,418 ms |
コンパイル使用メモリ | 207,736 KB |
最終ジャッジ日時 | 2025-01-06 18:44:44 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include<bits/stdc++.h> using namespace std; using P = pair<int, int>; const int M = 1000000007; vector<long long> a, ims; map<P, bool> mp; bool iswin(int l, int r) { if (mp.count(P(l, r))) return mp[P(l, r)]; long long x = ims[r] - ims[l]; if (a[l] * (r - l) >= x || a[r - 1] * (r - l) < x) return mp[P(l, r)] = true; int low = l, high = r; while (low + 1 < high) { int m = (low + high) / 2; if (a[m] * (r - l) >= x) high = m; else low = m; } return mp[P(l, r)] = !iswin(l, high) || !iswin(high, r); } int main() { int n; cin >> n; a = vector<long long>(n); ims = vector<long long>(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); for (int i = 0; i < n; ++i) { ims[i + 1] = ims[i] + a[i]; } cout << (iswin(0, n) ? "First\n" : "Second\n"); return 0; }