結果
問題 | No.761 平均値ゲーム |
ユーザー |
![]() |
提出日時 | 2018-12-09 19:10:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 6,308 bytes |
コンパイル時間 | 1,175 ms |
コンパイル使用メモリ | 111,712 KB |
実行使用メモリ | 11,372 KB |
最終ジャッジ日時 | 2024-09-16 09:05:16 |
合計ジャッジ時間 | 5,480 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <fstream>#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <sstream>#include <map>#include <set>#include <vector>#include <stack>#include <cmath>#include <queue>#include <random>using namespace std;#define INT_MAX_VALUE 2147483647#define LONG_LONG_MAX_VALUE 9223372036854775807#define ll long long#define ld long doublestruct XX{int s;vector<int> t;};class xxGreater {public:bool operator()(const XX& riLeft, const XX& riRight) const {//第2条件/*if((riLeft.s) == (riRight.s)){return riLeft.s < riRight.s;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)//プライオリティキューの場合は > で、top()すると値の小さいものがとれる}*///第1条件return (riLeft.s) < (riRight.s);}};struct edge{int ii;int to1;int to2;int l;int r;int w;int rank;};class rankGreater {public:bool operator()(const edge& riLeft, const edge& riRight) const {return (riLeft.rank) > (riRight.rank);}};//map<long long,long long> prime_f(long long n){// map<long long,long long>res;// for(int i=2;i*i<=n;i++){// while(n%i==0){// ++res[i];// n/=i;// }// }// if(n!=1)res[n]=1;// return res;//}//int n;////int dat[2*10000000];////int dat2[2*10000000];//int dat[10];//int dat2[10];////void init(int n_){// n=1;// while(n<n_)n*=2;// for(int i=0;i<2*n-1;i++){// dat[i]=0;// dat2[i]=0;// }//}////void initset(int k,int a){// k+=n-1;// dat[k]=a;// while(k>0){// k=(k-1)/2;// dat[k]=dat[k*2+1]+dat[k*2+2];// }//}//////[a,b)の間を[l,r]区間で比較しアップデート////引数のindexに注意////nは固定。initで計算すみ////update2(L[i],R[i]+1,0,0,n,D[i]);//void update2(int a,int b,int k,int l,int r,int v){//v更新値、区間は0-index// if(r<=a || b<=l)return;// if(a<=l && r<=b){// dat[k]+=dat2[k];// if(r-l>1){// dat2[k*2+1]+=dat2[k]/2;// dat2[k*2+1]+=dat2[k]/2;// }// dat2[k]=v*(r-l);// return;// }else{// update2(a,b,k*2+1,l,(l+r)/2,v);// update2(a,b,k*2+2,(l+r)/2,r,v);// return;// }//}////int query(int a,int b,int k,int l,int r){// if(r<=a || b<=l)return 0;// if(a<=l && r<=b){// dat[k]+=dat2[k];// if(r-l>1){// dat2[k*2+1]+=dat2[k]/2;// dat2[k*2+1]+=dat2[k]/2;// }// dat2[k]=0;// return dat[k];// }// else{// int vl=query(a,b,k*2+1,l,(l+r)/2);// int vr=query(a,b,k*2+2,(l+r)/2,r);// return vl+vr;// }//}edge G[2*10000000];//edge G[2*1000];int aa[2*10000000];//int aa[2*1000];int main(int argc, const char * argv[]){//scanf("%s",S);//scanf("%d",&N);//scanf("%lld %lld",&target1,&target2);//sscanf(tmp.c_str(),"%dd%d%d",&time[i], &dice[i], &z[i]);//getline(cin, target);//ifstream ifs("3.txt");//テスト用//ifs >> a;//ここから//入力高速化ios::sync_with_stdio(false);cin.tie(0);int N;cin >> N;vector<ll> a;for(int i=0;i<N;i++){ll tmp;cin >> tmp;a.push_back(tmp);}if(N==1){cout << "First" << endl;return 0;}ll wa[100000];for(int i=0;i<N;i++){if(i==0){wa[i]=a[i];}else{wa[i]=a[i]+wa[i-1];}}struct P{int l;int r;int w;};queue<int> que;que.push(0);G[0].l=0;G[0].r=N-1;G[0].rank=0;G[0].ii=0;int index=1;while(!que.empty()){edge tmp=G[que.front()];ll avg;if(tmp.l>=tmp.r){que.pop();continue;}if(a[tmp.l]==a[tmp.r]){que.pop();continue;}if(tmp.l-1>=0){avg=(wa[tmp.r]-wa[tmp.l-1])/(tmp.r-(tmp.l-1));if((wa[tmp.r]-wa[tmp.l-1])%(tmp.r-(tmp.l-1))>0){avg++;}}else{avg=wa[tmp.r]/(tmp.r+1);if(wa[tmp.r]%(tmp.r+1)>0){avg++;}}int mid=(int)(lower_bound(a.begin(),a.end(),avg)-a.begin());if(tmp.l<=mid-1){G[que.front()].to1=index;G[index].l=tmp.l;G[index].r=mid-1;G[index].rank=G[que.front()].rank+1;G[index].ii=index;if(mid-1<0)G[index].r=0;que.push(index);index++;}else{G[que.front()].to1=-1;}if(mid<=tmp.r){G[que.front()].to2=index;G[index].l=mid;G[index].r=tmp.r;G[index].rank=G[que.front()].rank+1;G[index].ii=index;que.push(index);index++;}else{G[que.front()].to2=-1;}que.pop();}//rankでソートsort(G,G+index,rankGreater());for(int i=0;i<index;i++){aa[G[i].ii]=i;}for(int i=0;i<index;i++){if(G[i].r==G[i].l || a[G[i].r]==a[G[i].l]){if(G[i].rank%2==0){G[i].w=1;}else{G[i].w=2;}}else{if(G[i].rank%2==0){if((G[i].to1!=0 && G[aa[G[i].to1]].w==1) || (G[i].to1!=0 && G[aa[G[i].to2]].w==1)){G[i].w=1;}else{G[i].w=2;}}else{if((G[i].to1!=0 && G[aa[G[i].to1]].w==2) || (G[i].to2!=0 && G[aa[G[i].to2]].w==2)){G[i].w=2;}else{G[i].w=1;}}}}if(G[index-1].w==1){cout << "First" << endl;}else{cout << "Second" << endl;}//ここまで//cout << "ans" << endl;//printf("%.0f\n",ans);//小数点以下表示なし//printf("%.7f\n",p);return 0;}