Submission #445993

#	Time	Username	Problem	Language	Result	Execution time	Memory
445993		grt	Sateliti (COCI20_satellti)	C++17	110 / 110	683 ms	19084 KiB

Main

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 1000 + 10, p = 31, q = 317, mod = 1e9 + 7;
int n, m;
char t[nax][nax];
int hsh[2 * nax][2 * nax], pot1[2 * nax], pot2[2 * nax];
pi ans;

int subrect(int a, int b, int c, int d) {
	int w = (hsh[c][d] - (ll)pot2[d - b + 1] * hsh[c][b - 1] - (ll)pot1[c - a + 1] * hsh[a - 1][d]) % mod;
	w = (w + (ll)(((ll) pot2[d - b + 1] * hsh[a - 1][b - 1])%mod) * pot1[c - a + 1]) % mod;
	if(w < 0) w += mod;
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> t[i][j];
		}
	}
	pot1[0] = pot2[0] = 1;
	for(int i = 1; i <= 2 * max(n, m); ++i) {
		pot1[i] = ((ll)pot1[i - 1] * p) % mod;
		pot2[i] = ((ll)pot2[i - 1] * q) % mod;
	}
	for(int i = 1; i <= 2 * n; ++i) {
		for(int j = 1; j <= 2 * m; ++j) {
			hsh[i][j] = ((ll)hsh[i - 1][j] * p + (ll)hsh[i][j - 1] * q - (ll)hsh[i - 1][j - 1] * p * q + (t[(i - 1) % n + 1][(j - 1) % m + 1] == '.' ? 1 : 2)) % mod;
			if(hsh[i][j] < 0) hsh[i][j] += mod;
		}
	}
	ans = {1, 1};
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(i == j && i == 1) continue;
			int low = 1, high = n, mid;
			while(low <= high) {
				mid = (low + high) / 2;
				if(subrect(ans.ST, ans.ND, ans.ST + mid - 1, ans.ND + m - 1) != subrect(i, j, i + mid - 1, j + m - 1)) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}
			high++;
			if(high == n + 1) continue;
			int row = high;
			low = 1; high = m;
			while(low <= high) {
				mid = (low + high) / 2;
				if(subrect(ans.ST + row - 1, ans.ND, ans.ST + row - 1, ans.ND + mid - 1) != subrect(i + row - 1, j, i + row - 1, j + mid - 1)) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}
			//cout << ans.ST << " " << ans.ND << " " << i << " " << j << " " << row << " " << high + 1 << "\n";
			if(t[(ans.ST + row - 2) % n + 1][(ans.ND + high - 1) % m + 1] == '.') {
				ans = {i, j};
			}
		}
	}
	for(int i = ans.ST; i < ans.ST + n; ++i) {
		for(int j = ans.ND; j < ans.ND + m; ++j) {
			cout << t[(i - 1) % n + 1][(j - 1) % m + 1];
		}
		cout << "\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60