oj.uz

Submission #1006148

# Submission time Handle Problem Language Result Execution time Memory
1006148 2024-06-23T13:34:20 Z BF001 Osmosmjerka (COCI17_osmosmjerka) C++17
60 / 160
 313 ms 189524 KB 
#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];
		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]  + hsh[k - 1][x][y]); 
			}
		}
	}

	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]);
					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
60.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 125532 KB Output is correct
2 Correct 10 ms 125444 KB Output is correct
3 Correct 10 ms 127832 KB Output is correct
4 Incorrect 11 ms 129628 KB Output isn't correct
5 Incorrect 14 ms 135772 KB Output isn't correct
6 Incorrect 22 ms 154460 KB Output isn't correct
7 Incorrect 125 ms 172976 KB Output isn't correct
8 Incorrect 313 ms 189524 KB Output isn't correct