結果
問題 |
No.1746 Sqrt Integer Segments
|
ユーザー |
![]() |
提出日時 | 2023-09-12 10:23:45 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 519 ms |
コンパイル使用メモリ | 31,360 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-06-29 23:02:09 |
合計ジャッジ時間 | 2,316 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
コンパイルメッセージ
main.c: In function 'f2': main.c:75:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration] 75 | write(1,wp,wbuf+sizeof wbuf-wp); | ^~~~~ main.c:76:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration] 76 | _exit(0); | ^~~~~ | _Exit main.c: At top level: main.c:79:1: warning: return type defaults to 'int' [-Wimplicit-int] 79 | main(){ | ^~~~
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); #define rd_skip() while(*rp++>=48) #define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);} #define SIEVE_N 1000000 unsigned sieve[SIEVE_N/2+1][2]; void mksieve(){ for(long i=3;i*i<SIEVE_N;i+=2){ if(sieve[i>>1][0]==0){ long k=i; for(long j=i*i>>1;j<SIEVE_N/2;j+=i){ sieve[j][0]=i; sieve[j][1]=k; k+=2; } } } } static inline unsigned long splitmix64(unsigned long x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } #define HH_BITS 19 #define HH_LEN (1<<HH_BITS) #define HH_MASK (HH_LEN-1) unsigned long hh[HH_LEN]; int c[HH_LEN]; long f1(){ char*rp=mmap(0l,1l<<25,1,2,0,0ll); rd(n); long z=0; unsigned long h=1; { unsigned long h2=h&HH_MASK; hh[h2]=h; z+=c[h2]++; } while(n--){ rd(a); while((a&3)==0){ a>>=2; } if((a&1)==0){ h^=splitmix64(2); a>>=1; } while(a>1){ h^=splitmix64(sieve[a>>1][0]?:a); a=sieve[a>>1][1]; } unsigned long h2=h&HH_MASK; while(hh[h2]!=0&&hh[h2]!=h){ h2=h2+1&HH_MASK; } hh[h2]=h; z+=c[h2]++; } return z; } void f2(long z){ char wbuf[64],*wp=wbuf+sizeof wbuf; wt(z); write(1,wp,wbuf+sizeof wbuf-wp); _exit(0); } main(){ mksieve(); f2(f1()); }