Submission #823615

#TimeUsernameProblemLanguageResultExecution timeMemory
823615EthanKim8683Osmosmjerka (COCI17_osmosmjerka)C++17
100 / 160
4072 ms8708 KiB
#include<bits/stdc++.h> using namespace std; using I=int; using C=char; using Lli=long long int; const I M=500; const I N=500; const Lli MOD=(1ll<<31)-1; const Lli BAS=(1ll<<17)-1; I dx[]{-1,-1,-1,0,0,1,1,1},dy[]{-1,0,1,-1,1,-1,0,1}; C blks[M][N+1]; map<Lli,I>cnts; I main(){ cin.tie(0)->sync_with_stdio(0); I m,n,k;cin>>m>>n>>k; for(I i=0;i<m;i++)cin>>blks[i]; I len=min(max(n,m),k); for(I i=0;i<m;i++)for(I j=0;j<n;j++)for(I l=0;l<8;l++){ Lli hsh=0; for(I o=0;o<len;o++)hsh=(hsh*BAS+blks[((i+o*dx[l])%m+m)%m][((j+o*dy[l])%n+n)%n])%MOD; cnts[hsh]++; } Lli num=0,den=8*n*m; den*=den; for(auto[hsh,cnt]:cnts)num+=(Lli)cnt*cnt; Lli fac=gcd(num,den); printf("%lli/%lli\n",num/fac,den/fac); }
#Verdict Execution timeMemoryGrader output
Fetching results...