oj.uz

Submission #445993

# Submission time Handle Problem Language Result Execution time Memory
445993 2021-07-20T11:20:20 Z grt Sateliti (COCI20_satellti) C++17
110 / 110
 683 ms 19084 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 48 ms 4384 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 54 ms 4420 KB Output is correct
12 Correct 56 ms 4492 KB Output is correct
13 Correct 47 ms 4500 KB Output is correct
14 Correct 52 ms 4508 KB Output is correct
15 Correct 47 ms 4508 KB Output is correct
16 Correct 61 ms 4512 KB Output is correct
17 Correct 52 ms 4512 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 48 ms 4384 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 54 ms 4420 KB Output is correct
12 Correct 56 ms 4492 KB Output is correct
13 Correct 47 ms 4500 KB Output is correct
14 Correct 52 ms 4508 KB Output is correct
15 Correct 47 ms 4508 KB Output is correct
16 Correct 61 ms 4512 KB Output is correct
17 Correct 52 ms 4512 KB Output is correct
18 Correct 617 ms 18572 KB Output is correct
19 Correct 10 ms 9548 KB Output is correct
20 Correct 9 ms 588 KB Output is correct
21 Correct 579 ms 18996 KB Output is correct
22 Correct 650 ms 19004 KB Output is correct
23 Correct 572 ms 19024 KB Output is correct
24 Correct 683 ms 19000 KB Output is correct
25 Correct 565 ms 19084 KB Output is correct
26 Correct 637 ms 19000 KB Output is correct
27 Correct 652 ms 18988 KB Output is correct