Submission #855764

#	Time	Username	Problem	Language	Result	Execution time	Memory
855764		serifefedartar	Sateliti (COCI20_satellti)	C++17	110 / 110	689 ms	97208 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll MAXN = 1005;

const ll P = 79;
const ll Q = 83;
int n, m;
ll powP[2*MAXN], powQ[2*MAXN], v[2*MAXN][2*MAXN], tmp[2*MAXN][2*MAXN];
ll pref[2*MAXN][2*MAXN], invP[2*MAXN], invQ[2*MAXN];
ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

ll get(int row1, int col1, int len_row, int len_col) {
	int row2 = row1 + len_row - 1;
	int col2 = col1 + len_col - 1;
	ll ret = (pref[row2][col2] - pref[row1-1][col2] - pref[row2][col1-1] + pref[row1-1][col1-1]) % MOD;
	while (ret < 0)
		ret += MOD;

	ret = (ret * invP[row1 - 1]) % MOD;
	ret = (ret * invQ[col1 - 1]) % MOD;
	return ret;
}

bool comp(int nrow, int ncol, int row, int col) {
	int L = 1;
	int R = n*m;
	int same = 0;

	while (R >= L) {
		int mid = L + (R-L)/2;
		int qrow = (mid + m - 1) / m;
		int qcol = (mid % m != 0 ? mid % m : m);
		bool check = true;

		if (qrow - 1 >= 1 && get(row, col, qrow - 1, m) != get(nrow, ncol, qrow - 1, m))
			check = false;

		if (get(row, col, qrow, qcol) != get(nrow, ncol, qrow, qcol))
			check = false;

		if (check) {
			same = mid;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	if (same == n * m)
		return false;

	same++;
	int diff_row = (same + m - 1) / m;
	int diff_col = (same % m != 0 ? same % m : m);
	if (v[nrow + diff_row - 1][ncol + diff_col - 1] < v[row + diff_row - 1][col + diff_col - 1])
		return true;
	return false;
}

int main() {
	fast
	powP[0] = powQ[0] = invP[0] = invQ[0] = 1;
	for (int i = 1; i < 2*MAXN; i++) {
		powP[i] = (powP[i-1] * P) % MOD;
		invP[i] = expo(powP[i], MOD-2);
		powQ[i] = (powQ[i-1] * Q) % MOD;
		invQ[i] = expo(powQ[i], MOD-2);
	}
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++)
			v[i][j] = (s[j-1] == '.');
	}

	for (int i = n+1; i <= 2*n; i++) {
		for (int j = 1; j <= m; j++)
			v[i][j] = v[i-n][j];
	}

	for (int j = m+1; j <= 2*m; j++) {
		for (int i = 1; i <= 2*n; i++)
			v[i][j] = v[i][j-m];
	}

	for (int i = 1; i <= 2*n; i++) {
		for (int j = 1; j <= 2*m; j++) {
			tmp[i][j] = v[i][j];
			v[i][j] = ((v[i][j] * powP[i] % MOD) * powQ[j]) % MOD;
		}
	}

	for (int i = 1; i <= 2*n; i++) {
		for (int j = 1; j <= 2*m; j++) {
			pref[i][j] = (pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + v[i][j]) % MOD;
			while (pref[i][j] < 0)
				pref[i][j] += MOD;
		}
	}

	int row = 1, col = 1;
	for (int i = 1; i + n - 1 <= 2*n; i++) {
		for (int j = 1; j + m - 1 <= 2*m; j++) {
			if (comp(i, j, row, col)) {
				row = i, col = j;
			}
		}
	}

	for (int i = row; i <= row + n - 1; i++) {
		for (int j = col; j <= col + m - 1; j++)
			cout << (tmp[i][j] ? '.' : '*');
		cout << "\n";
	}
}

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