Submission #870785

#TimeUsernameProblemLanguageResultExecution timeMemory
870785vjudge1Osmosmjerka (COCI17_osmosmjerka)C++17
160 / 160
2156 ms19604 KiB
/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog. Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include <bits/stdc++.h> #pragma GCC optimize(3) using namespace std; #define N 501 int di[8]={0, 1, 1, 1, 0, -1, -1, -1}, dj[8]={-1, -1, 0, 1, 1, 1, 0, -1}; int n, m, k; string g[N]; bool vis[N][N]; unsigned long long h[2*N*N+1], a1, a2, a3, pB=1, c[8*N*N], cnt; int main() { cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k, k=min(n*m, k); for(int i=0; i<k; ++i) pB*=29; for(int i=0; i<n; ++i) cin >> g[i]; for(int d=0; d<8; ++d) { for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { if(vis[i][j]) continue; int a=0, ci=i, cj=j; while(!vis[ci][cj]) { vis[ci][cj]=1; h[++a]=g[ci][cj]-'a'+1; ci=(ci+di[d]+n)%n; cj=(cj+dj[d]+m)%m; } for(int l=a; l+1<a+k; l+=a) memcpy(h+l+1, h+1, 8*a); for(int l=1; l<a+k; ++l) h[l]+=h[l-1]*29; for(int l=0; l<a; ++l) c[cnt++]=h[l+k]-h[l]*pB; } } memset(vis, 0, sizeof(vis)); } sort(c, c+8*n*m); for(int i=0, j=0; i<8*n*m; i=j) { while (j<8*n*m&&c[j]==c[i]) j++; a1+=(unsigned long long)(j-i)*(j-i); } a2=n*m*8, a2*=a2; int a3 = gcd(a1,a2); cout << a1/a3 << "/" << a2/a3; }
#Verdict Execution timeMemoryGrader output
Fetching results...