Submission #1006154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1006154	2024-06-23T13:37:39 Z	BF001	Osmosmjerka (COCI17_osmosmjerka)	C++17	140 / 160	1313 ms	222036 KB

osmosmjerka

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

#define N 505
#define log 30
#define fi first
#define se second
#define int long long

typedef pair<int, int> ii;

ii par[log + 2][N][N];
int hsh[log + 2][N][N], pw[log + 2], base = 32, md = 1e9 + 7, n, m, len;
map<int, int> dd;

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] = s[i][j] - 'a' + 1;
			par[0][i][j] = {(i + dx + n) % n, (j + dy + m) % m};
		}
	}
	pw[0] = base;
	for (int k = 1; k <= log; k++){
		pw[k] = pw[k - 1] * pw[k - 1] % md;
		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] * pw[k - 1] % md + hsh[k - 1][x][y]) % md; 
			}
		}
	}

	int dis = len;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			int x = i, y = j;
			int cnt = 0;
			dis = len;
			for (int k = log; k >= 0; k--){
				if ((1ll << k) <= dis){
					dis -= (1ll << k);
					int tx = x;
					cnt = (cnt * pw[k] + hsh[k][x][y]) % md;
					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);
		}
	}

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

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

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

    return 0;
}     

Subtask #1

140.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	125532 KB	Output is correct
2	Correct	10 ms	125580 KB	Output is correct
3	Correct	11 ms	127576 KB	Output is correct
4	Correct	12 ms	129744 KB	Output is correct
5	Correct	18 ms	136028 KB	Output is correct
6	Correct	37 ms	157012 KB	Output is correct
7	Incorrect	460 ms	191736 KB	Output isn't correct
8	Correct	1313 ms	222036 KB	Output is correct