# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
823629 | EthanKim8683 | Osmosmjerka (COCI17_osmosmjerka) | C++17 | 4043 ms | 24636 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using I=int;
using C=char;
using Lli=long long int;
using B=bool;
const I M=500;
const I N=500;
const Lli MOD=(1ll<<31)-1;
const Lli BAS=37187;
I dx[]{-1,-1,-1,0,0,1,1,1},dy[]{-1,0,1,-1,1,-1,0,1};
C blks[M][N+1];
B viss[N][M][8];
Lli hshs[N][M][8];
map<Lli,I>cnts;
I m,n;
B ins(I i,I j){
return i>=0&&i<m&&j>=0&&j<n;
}
C get(I i,I j,I dir,I len){
return blks[((i+len*dx[dir])%m+m)%m][((j+len*dy[dir])%n+n)%n];
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I k;cin>>m>>n>>k;
for(I i=0;i<m;i++)cin>>blks[i];
I len=min(n*m,k);
Lli pow=1;
for(I i=1;i<=len;i++)pow=pow*BAS%MOD;
for(I i=0;i<8;i++)for(I j=0;j<m;j++)for(I l=0;l<n;l++){
if(viss[j][l][i])continue;
I x=j,y=l;
for(;ins(x,y);x-=dx[i],y-=dy[i]);
x+=dx[i],y+=dy[i];
Lli hsh=0;
for(I o=0;o<len;o++)hsh=(hsh*BAS+get(x,y,i,o))%MOD;
for(;ins(x,y);x+=dx[i],y+=dy[i]){
hshs[x][y][i]=hsh,viss[x][y][i]=1;
hsh=((hsh*BAS+get(x,y,i,len)-get(x,y,i,0)*pow)%MOD+MOD)%MOD;
}
}
for(I i=0;i<m;i++)for(I j=0;j<n;j++)for(I l=0;l<8;l++)cnts[hshs[i][j][l]]++;
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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |