結果
問題 | No.761 平均値ゲーム |
ユーザー |
|
提出日時 | 2020-02-22 20:22:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 568 bytes |
コンパイル時間 | 808 ms |
コンパイル使用メモリ | 76,688 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2024-10-09 20:48:23 |
合計ジャッジ時間 | 7,458 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
main.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 24 | main() | ^~~~
ソースコード
#include<iostream>#include<map>using namespace std;int N;long A[1<<17],S[1<<17];map<pair<int,int>,bool>M;bool f(int L,int R){if(L==R)return false;if(M.find(make_pair(L,R))!=M.end())return M[make_pair(L,R)];long sum=S[R]-S[L];int l=L-1,r=R;while(r-l>1){int m=l+r>>1;if(A[m]*(R-L)>=sum)r=m;else l=m;}bool ans=false;if(L<r)if(!f(r,R))ans=true;if(r<R)if(!f(L,r))ans=true;return M[make_pair(L,R)]=ans;}main(){cin>>N;for(int i=0;i<N;i++)cin>>A[i];for(int i=0;i<N;i++)S[i+1]=S[i]+A[i];cout<<(f(0,N)?"First":"Second")<<endl;}