結果
問題 | No.761 平均値ゲーム |
ユーザー | butsurizuki |
提出日時 | 2018-12-07 13:05:39 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 3,087 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 31,176 KB |
実行使用メモリ | 30,476 KB |
最終ジャッジ日時 | 2023-10-12 03:41:02 |
合計ジャッジ時間 | 7,512 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
9,944 KB |
testcase_01 | AC | 3 ms
9,916 KB |
testcase_02 | AC | 2 ms
5,760 KB |
testcase_03 | AC | 3 ms
10,004 KB |
testcase_04 | AC | 3 ms
9,964 KB |
testcase_05 | AC | 2 ms
10,000 KB |
testcase_06 | AC | 2 ms
10,008 KB |
testcase_07 | AC | 2 ms
9,924 KB |
testcase_08 | AC | 2 ms
9,912 KB |
testcase_09 | AC | 2 ms
9,996 KB |
testcase_10 | AC | 2 ms
9,992 KB |
testcase_11 | AC | 2 ms
9,968 KB |
testcase_12 | AC | 2 ms
9,912 KB |
testcase_13 | AC | 2 ms
5,808 KB |
testcase_14 | AC | 2 ms
9,860 KB |
testcase_15 | AC | 2 ms
9,944 KB |
testcase_16 | AC | 2 ms
9,960 KB |
testcase_17 | AC | 2 ms
9,872 KB |
testcase_18 | AC | 2 ms
9,964 KB |
testcase_19 | AC | 2 ms
9,932 KB |
testcase_20 | AC | 3 ms
9,856 KB |
testcase_21 | AC | 2 ms
9,968 KB |
testcase_22 | AC | 2 ms
9,996 KB |
testcase_23 | AC | 3 ms
9,932 KB |
testcase_24 | AC | 2 ms
9,868 KB |
testcase_25 | AC | 1 ms
5,892 KB |
testcase_26 | AC | 2 ms
9,964 KB |
testcase_27 | AC | 2 ms
5,824 KB |
testcase_28 | AC | 3 ms
9,924 KB |
testcase_29 | AC | 2 ms
10,008 KB |
testcase_30 | AC | 2 ms
9,936 KB |
testcase_31 | AC | 3 ms
9,944 KB |
testcase_32 | AC | 3 ms
9,992 KB |
testcase_33 | AC | 76 ms
23,392 KB |
testcase_34 | AC | 86 ms
24,424 KB |
testcase_35 | AC | 9 ms
10,800 KB |
testcase_36 | AC | 48 ms
20,900 KB |
testcase_37 | AC | 70 ms
22,376 KB |
testcase_38 | AC | 70 ms
22,376 KB |
testcase_39 | AC | 91 ms
29,088 KB |
testcase_40 | AC | 86 ms
24,648 KB |
testcase_41 | AC | 82 ms
23,976 KB |
testcase_42 | AC | 92 ms
26,176 KB |
testcase_43 | AC | 17 ms
13,280 KB |
testcase_44 | AC | 57 ms
21,300 KB |
testcase_45 | AC | 80 ms
23,724 KB |
testcase_46 | AC | 44 ms
19,448 KB |
testcase_47 | AC | 46 ms
19,424 KB |
testcase_48 | AC | 7 ms
10,500 KB |
testcase_49 | AC | 93 ms
25,880 KB |
testcase_50 | AC | 13 ms
11,264 KB |
testcase_51 | AC | 8 ms
10,576 KB |
testcase_52 | AC | 9 ms
10,716 KB |
testcase_53 | AC | 92 ms
25,936 KB |
testcase_54 | AC | 52 ms
21,356 KB |
testcase_55 | AC | 91 ms
29,516 KB |
testcase_56 | AC | 27 ms
13,080 KB |
testcase_57 | AC | 95 ms
25,996 KB |
testcase_58 | AC | 16 ms
11,672 KB |
testcase_59 | AC | 88 ms
25,904 KB |
testcase_60 | AC | 27 ms
14,688 KB |
testcase_61 | AC | 99 ms
29,836 KB |
testcase_62 | AC | 95 ms
29,428 KB |
testcase_63 | AC | 20 ms
14,200 KB |
testcase_64 | AC | 84 ms
23,912 KB |
testcase_65 | AC | 35 ms
15,120 KB |
testcase_66 | AC | 8 ms
10,620 KB |
testcase_67 | AC | 28 ms
12,960 KB |
testcase_68 | AC | 11 ms
11,012 KB |
testcase_69 | AC | 73 ms
22,412 KB |
testcase_70 | AC | 48 ms
21,024 KB |
testcase_71 | AC | 22 ms
12,388 KB |
testcase_72 | AC | 11 ms
10,884 KB |
testcase_73 | AC | 32 ms
15,072 KB |
testcase_74 | AC | 20 ms
12,060 KB |
testcase_75 | AC | 43 ms
19,056 KB |
testcase_76 | AC | 28 ms
14,940 KB |
testcase_77 | AC | 73 ms
22,636 KB |
testcase_78 | AC | 49 ms
19,820 KB |
testcase_79 | AC | 18 ms
12,012 KB |
testcase_80 | AC | 15 ms
13,176 KB |
testcase_81 | AC | 12 ms
11,204 KB |
testcase_82 | AC | 60 ms
22,196 KB |
testcase_83 | AC | 103 ms
27,264 KB |
testcase_84 | AC | 103 ms
30,476 KB |
testcase_85 | AC | 106 ms
27,376 KB |
testcase_86 | AC | 106 ms
29,988 KB |
testcase_87 | AC | 110 ms
30,016 KB |
testcase_88 | AC | 105 ms
27,656 KB |
testcase_89 | AC | 105 ms
27,180 KB |
testcase_90 | AC | 104 ms
27,124 KB |
testcase_91 | AC | 104 ms
27,148 KB |
testcase_92 | AC | 103 ms
26,760 KB |
testcase_93 | AC | 2 ms
9,968 KB |
testcase_94 | AC | 2 ms
9,964 KB |
testcase_95 | AC | 18 ms
10,772 KB |
testcase_96 | AC | 20 ms
10,912 KB |
testcase_97 | AC | 18 ms
10,776 KB |
testcase_98 | AC | 54 ms
21,456 KB |
testcase_99 | AC | 59 ms
20,508 KB |
ソースコード
//debug #include<stdio.h> #include<stdlib.h> #define size 1048576 #define llinf 4154118101919364364 long 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); if(n<1 || 100000<n){while(1){i++;}} for(i=1;i<=n;i++){ scanf("%lld",&a[i]); if(a[i]<1 || 1000000000000<a[i]){while(1){j++;}} 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; }