Submission #107025

#	Time	Username	Problem	Language	Result	Execution time	Memory
107025		gs14004	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	1750 ms	25452 KiB

osmosmjerka

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 505;
const int mod1 = 1e9 + 696969;
const int mod2 = 1e9 + 409;

vector<lint> hashes;
int n, m, k;
char str[MAXN][MAXN];
int spt1[2][MAXN][MAXN], spt2[2][MAXN][MAXN];
int hsh0[MAXN][MAXN], hsh1[MAXN][MAXN], nhsh0[MAXN][MAXN], nhsh1[MAXN][MAXN];
lint pwr1[30], pwr2[30];

void Do(int dx, int dy){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			spt1[0][i][j] = spt2[0][i][j] = str[i][j];
			hsh0[i][j] = hsh1[i][j] = 0;
		}
	}
	for(int i=1; i<=30; i++){
		if((k >> (i-1)) & 1){
			for(int j=0; j<n; j++){
				for(int k=0; k<m; k++){
					int nxtX = j - (dx<<(i-1));
					int nxtY = k - (dy<<(i-1));
					nxtX %= n, nxtY %= m;
					nxtX += n, nxtY += m;
					nxtX %= n, nxtY %= m;
					nhsh0[j][k] = (hsh0[nxtX][nxtY] * pwr1[i-1] + spt1[(i-1)%2][j][k]) % mod1;
					nhsh1[j][k] = (hsh1[nxtX][nxtY] * pwr2[i-1] + spt2[(i-1)%2][j][k]) % mod2;
				}
			}
			memcpy(hsh0, nhsh0, sizeof(hsh0));
			memcpy(hsh1, nhsh1, sizeof(hsh1));
		}
		for(int j=0; j<n; j++){
			for(int k=0; k<m; k++){
				int nxtX = j - (dx<<(i-1));
				int nxtY = k - (dy<<(i-1));
				nxtX %= n, nxtY %= m;
				nxtX += n, nxtY += m;
				nxtX %= n, nxtY %= m;
				spt1[i%2][j][k] = (spt1[(i-1)%2][nxtX][nxtY] * pwr1[i-1] + spt1[(i-1)%2][j][k]) % mod1;
				spt2[i%2][j][k] = (spt2[(i-1)%2][nxtX][nxtY] * pwr2[i-1] + spt2[(i-1)%2][j][k]) % mod2;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			lint ans = 1ll * hsh0[i][j] * mod2 + hsh1[i][j];
			hashes.push_back(ans);
		}
	}
}

lint gcd(lint x, lint y){ return y ? gcd(y, x%y) : x; }

int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0; i<n; i++) scanf("%s", str[i]);
	pwr1[0] = pwr2[0] = 257;
	for(int i=1; i<30; i++){
		pwr1[i] = 1ll * pwr1[i-1] * pwr1[i-1] % mod1;
		pwr2[i] = 1ll * pwr2[i-1] * pwr2[i-1] % mod2;
	}
	lint Y = 64ll * n * m * n * m;
	for(int i=-1; i<=1; i++){
		for(int j=-1; j<=1; j++){
			if(i || j) Do(i, j);
		}
	}
	lint X = 0;
	sort(hashes.begin(), hashes.end());
	for(int i=0; i<hashes.size(); ){
		int e = i;
		while(e < hashes.size() && hashes[e] == hashes[i]) e++;
		X += 1ll * (e - i) * (e - i);
		i = e;
	}
	lint g = gcd(X, Y);
	X /= g, Y /= g;
	printf("%lld/%lld\n", X, Y);
}

Compilation message (stderr)

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<hashes.size(); ){
               ~^~~~~~~~~~~~~~
osmosmjerka.cpp:79:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < hashes.size() && hashes[e] == hashes[i]) e++;
         ~~^~~~~~~~~~~~~~~
osmosmjerka.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%s", str[i]);
                         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 160 / 160