結果
問題 | No.761 平均値ゲーム |
ユーザー |
|
提出日時 | 2018-12-07 04:49:37 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 2,983 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 32,384 KB |
実行使用メモリ | 23,608 KB |
最終ジャッジ日時 | 2024-09-14 03:20:41 |
合計ジャッジ時間 | 6,451 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include<stdio.h>#include<stdlib.h>#define size 1048576#define llinf 4154118101919364364long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}typedef struct{long long val;long long node;}sd;int sdsortfnc(const void *a,const void *b){if(((sd*)a)->val > ((sd*)b)->val){return -1;}if(((sd*)a)->val < ((sd*)b)->val){return 1;}return 0;}typedef struct{long long st;long long fi;}rs;typedef struct{long long st;long long kz;}mkj;int sortfnc(const void *a,const void *b){if(((rs*)a)->st == ((rs*)b)->st){return 0;}if(((rs*)a)->st < ((rs*)b)->st){return -1;}return 1;}void makemkj(rs g[],mkj x[],long long n){long long i,ms=0,nst=g[0].st;for(i=1;i<n;i++){if(g[i].st!=g[i-1].st){x[nst].kz=i-ms;x[nst].st=ms;nst=g[i].st;ms=i;}}x[nst].kz=n-ms;x[nst].st=ms;}long long search(long long x,long long a[],long long n){long long st=0,fi=n-1,te;while(st<=fi){te=(st+fi)/2;if(a[te]<x){st=te+1;}else{fi=te-1;}}return st;}long long vid=0,eid=0,color[size]={0};long long n,a[size],rw[size]={0};void grep(long long s,long long f,long long pid,rs g[]){long long nv=vid,te,pt;vid++;if(pid!=-1){g[eid].st=pid;g[eid].fi=nv;eid++;g[eid].fi=pid;g[eid].st=nv;eid++;}if(a[s]==a[f]){return;}te=llceil(rw[f]-rw[s-1],f-s+1);pt=search(te,&a[s],f-s+1);pt+=s;//printf("%lld:%lld %lld %lld %lld\n",nv,s,f,te,pt);grep(s,pt-1,nv,g);grep(pt,f,nv,g);return;}long long dist[size];void dfs(long long t,long long l,rs g[],mkj x[]){long long i;if(dist[t]<=l){return;}dist[t]=l;for(i=x[t].st;i<x[t].st+x[t].kz;i++){dfs(g[i].fi,l+1,g,x);}}int main(void){long long i,j,fl,nv,fn=0,sn=0;rs g[size];mkj x[size];sd dat[size];scanf("%lld",&n);for(i=1;i<=n;i++){scanf("%lld",&a[i]);rw[i]=rw[i-1]+a[i];}if(n==1){printf("First\n");return 0;}//printf("ok\n");grep(1,n,-1,g);//printf("ok\n");qsort(g,eid,sizeof(g[0]),sortfnc);//printf("ok\n");makemkj(g,x,eid);//printf("ok\n");for(i=0;i<vid;i++){dist[i]=llinf;}dfs(0,0,g,x);for(i=0;i<vid;i++){dat[i].val=dist[i];dat[i].node=i;}qsort(dat,vid,sizeof(dat[0]),sdsortfnc);for(i=0;i<vid;i++){fl=0;nv=dat[i].node;for(j=x[nv].st;j<x[nv].st+x[nv].kz;j++){if(dist[g[j].fi]<dist[nv]){continue;}fl|=color[g[j].fi];}if(fl==0 || fl==3){color[nv]=(dist[nv]%2)+1;}else{color[nv]=fl;}if(color[nv]==1){fn++;}else{sn++;}}//printf("<%lld %lld>\n",fn,sn);for(i=0;i<vid;i++){//printf("[%lld:%lld]\n",i,color[i]);}if(color[0]==1){printf("First\n");}else{printf("Second\n");}return 0;}