結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2019-06-26 22:02:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 1,729 ms |
コンパイル使用メモリ | 170,180 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 05:04:20 |
合計ジャッジ時間 | 6,518 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }#define FOR(i,a,b) for(ll i=(a);i<(b);++i)#define ALL(v) (v).begin(), (v).end()#define p(s) cout<<(s)<<endl#define p2(s, t) cout << (s) << " " << (t) << endl#define br() p("")#define pn(s) cout << (#s) << " " << (s) << endl#define p_yes() p("Yes")#define p_no() p("No")const ll mod = 1e9 + 7;const ll inf = 1e18;void vprint(vector<ll> A){ll L = A.size();FOR(i, 0, L){if(i) cout << ' ';cout << A[i];}cout << endl;}struct AccSum{vector<ll> Ac;ll L;AccSum(){}// A : 1 2 3 4// Ac: 0 1 3 6 10// [1, 2] == 5, それはAc[3]-Ac[1]void initialize(vector<ll> &A){L = A.size();Ac.resize(L+1);FOR(i, 0, L){Ac[i+1] = Ac[i] + A[i];}}// sum of [a, b]ll sum(ll a, ll b){if(a<0) return -1;if(b>L-1) return -1;return Ac[b+1] - Ac[a];}};ll N;vector<ll> A;AccSum accSum;// [L, R)内でmeanで切ったときのindexを返すll my_binary_search(ll L, ll R, double mean){if(A[L]>=mean) return L;if(A[R-1]<mean) return R;ll left = L;ll right= R-1;while(left+1!=right){ll center = (left+right)/2;if(A[center]<mean){left = center;}else{right = center;}}return right;}// [L, R)bool can_win(ll L, ll R){// br();// cout << "can_win " << L << ' ' << R << endl;if(L+1==R) return true; // 1つll n = R-L;ll sum = accSum.sum(L, R-1);double mean = (double)sum/n;// pn(sum);// pn(n);// pn(mean);ll mean_index = my_binary_search(L, R, mean);// pn(mean_index);if(mean_index==L) return true; // 全部取れるif(!can_win(L, mean_index) || !can_win(mean_index, R)){return true;}else{return false;}}int main(){cin.tie(0);ios::sync_with_stdio(false);// inputcin >> N;A.resize(N);FOR(i, 0, N){cin >> A.at(i);}accSum.initialize(A);// pn(accSum.sum(1, 4));// return 0;if(can_win(0, N)){p("First");}else{p("Second");}return 0;}