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