Submission #1006180

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1006180	2024-06-23T14:02:13 Z	BF001	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	1476 ms	224348 KB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;

#define N 505
#define log 30
#define fi first
#define se second
#define M 2

typedef pair<int, int> ii;

ii par[log + 2][N][N];
int n, m, len;
int base[M] = {32, 75};
long long pw[M][log + 2], md[M] = {1000000007, 1000000009};


struct hst
{
	long long val[M];
	hst(){
		memset(val, 0, sizeof(val));
	}
	void add(hst& a, int len){
		for (int i = 0; i <= 1; i++){
			val[i] = (1ll * val[i] * pw[i][len] + a.val[i]) % md[i];
		}
	}
};

bool operator < (const hst& a, const hst& b){
	for (int i = 0; i <= 1; i++){
		if (a.val[i] != b.val[i]) return a.val[i] < b.val[i];
	}
	return 0;
}

map<hst, long long> dd;
hst hsh[log + 2][N][N];

char s[N][N];

void solve(int dx, int dy){
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			hsh[0][i][j].val[0] = hsh[0][i][j].val[1] = s[i][j] - 'a' + 1;
			par[0][i][j] = {(i + dx + n) % n, (j + dy + m) % m};
		}
	}
	pw[0][0] = base[0];
	pw[1][0] = base[1];
	for (int k = 1; k <= log; k++){
		pw[0][k] = pw[0][k - 1] * pw[0][k - 1] % md[0];
		pw[1][k] = pw[1][k - 1] * pw[1][k - 1] % md[1];
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				par[k][i][j] = par[k - 1][par[k - 1][i][j].fi][par[k - 1][i][j].se];
				int x = par[k - 1][i][j].fi;
				int y = par[k - 1][i][j].se;
				hsh[k][i][j] = hsh[k - 1][i][j];
				hsh[k][i][j].add(hsh[k - 1][x][y], k - 1); 
			}
		}
	}

	int dis = len;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			int x = i, y = j;
			hst cnt;
			dis = len;
			for (int k = log; k >= 0; k--){
				if ((1ll << k) <= dis){
					dis -= (1ll << k);
					int tx = x;
					cnt.add(hsh[k][x][y], k);
					x = par[k][x][y].fi;
					y = par[k][tx][y].se;
				}
			}
			dd[cnt]++;
		}
	}
}	

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> n >> m >> len;
    for (int i = 0; i < n; i++){
    	for (int j = 0; j < m; j++) cin >> s[i][j];
    }  

	for (int i = -1; i <= 1; i++){
		for (int j = -1; j <= 1; j++){
			if (i == 0 && j == 0) continue;
			solve(i, j);
		}
	}

	long long t = 0, mm = 1ll * (n * m * 8) * (n * m * 8);
	for (auto x : dd){
		t += x.se * x.se;
	}

	long long gcd = __gcd(t, mm);
	t /= gcd, mm /= gcd;

	cout << t << "/" << mm;

    return 0;
}     

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	189020 KB	Output is correct
2	Correct	18 ms	189168 KB	Output is correct
3	Correct	17 ms	189272 KB	Output is correct
4	Correct	20 ms	189124 KB	Output is correct
5	Correct	21 ms	189272 KB	Output is correct
6	Correct	48 ms	191824 KB	Output is correct
7	Correct	456 ms	208212 KB	Output is correct
8	Correct	1476 ms	224348 KB	Output is correct