oj.uz

Submission #1006171

# Submission time Handle Problem Language Result Execution time Memory
1006171 2024-06-23T13:58:05 Z BF001 Osmosmjerka (COCI17_osmosmjerka) C++17
140 / 160
 520 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int, int> ii;

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

struct hst
{
	int val[M];
	hst(){
		memset(val, 0, sizeof(val));
	}
	void add(hst& a, int len){
		for (int i = 0; i <= 1; i++){
			val[i] = (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, int> 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);
		}
	}

	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 19 ms 191064 KB Output is correct
2 Correct 19 ms 193116 KB Output is correct
3 Correct 19 ms 195308 KB Output is correct
4 Correct 19 ms 197384 KB Output is correct
5 Correct 24 ms 203612 KB Output is correct
6 Correct 50 ms 222800 KB Output is correct
7 Correct 520 ms 257620 KB Output is correct
8 Runtime error 426 ms 262144 KB Execution killed with signal 9