oj.uz

Submission #823615

# Submission time Handle Problem Language Result Execution time Memory
823615 2023-08-12T21:54:01 Z EthanKim8683 Osmosmjerka (COCI17_osmosmjerka) C++17
100 / 160
 4000 ms 8708 KB 
#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);
}

Subtask #1
100.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 424 KB Output is correct
6 Incorrect 120 ms 1784 KB Output isn't correct
7 Incorrect 2609 ms 8708 KB Output isn't correct
8 Execution timed out 4072 ms 8604 KB Time limit exceeded