Submission #1012576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012576		Jawad_Akbar_JJ	Sateliti (COCI20_satellti)	C++17	110 / 110	902 ms	37716 KiB

Main

#include <iostream>

using namespace std;
#define int long long
const int N = 2005;
int calc[N][N], p = 101, q = 727, mod = 1e9 + 7, n, m;
int pP[N], pInv[N];
int qP[N], qInv[N];
char a[N][N];

int power(int a,int b){
	if (b == 1)
		return a;
	int ans = power(a,b / 2);
	ans = ans * ans % mod;
	if (b % 2)
		ans = ans * a % mod;
	return ans;
}

int get1(int i,int j,int k){
	int rs = k / m;
	if (rs == 0)
		return 0;
	int i2 = i + rs - 1;
	int j2 = j + m - 1;
	int Ans = calc[i2][j2] - calc[i2][j-1] - calc[i-1][j2] + calc[i-1][j-1];
	return ((Ans % mod) + mod) % mod;
}
int get2(int i,int j,int k){
	i += k / m;
	k %= m;
	if (k == 0)
		return 0;
	int i2 = i;
	int j2 = j + k - 1;
	int Ans = calc[i2][j2] - calc[i2][j-1] - calc[i-1][j2] + calc[i-1][j-1];
	return ((Ans % mod) + mod) % mod;
}

int get(int i,int j,int k){
	int Ans = get1(i,j,k) + get2(i,j,k);
	Ans = Ans * pInv[i-1] % mod;
	Ans = Ans * qInv[j-1] % mod;
	return Ans;
}

signed main(){

	pP[0] = qP[0] = pInv[0] = qInv[0] = 1;

	for (int i=1;i<N;i++){
		pP[i] = pP[i-1] * p % mod;
		qP[i] = qP[i-1] * q % mod;
		pInv[i] = power(pP[i],mod - 2);
		qInv[i] = power(qP[i],mod - 2);
	}

	cin>>n>>m;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			cin>>a[i][j];
			a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
		}

	for (int i=1;i<=2*n;i++)
		for (int j=1;j<=2*m;j++){
			calc[i][j] = calc[i-1][j] + calc[i][j-1] - calc[i-1][j-1];
			calc[i][j] += (pP[i] * qP[j] % mod) * a[i][j] % mod;
			calc[i][j] %= mod;
		}

	int bst_i = 1,bst_j = 1;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (get(i,j,n * m) == get(bst_i, bst_j, n * m))
				continue;
			int l = 0,r = n * m;

			while (l + 1 < r){
				int mid = (l + r) / 2;
				if (get(i,j,mid) == get(bst_i, bst_j, mid))
					l = mid;
				else
					r = mid;
			}
			int ja = -1 + r % m;
			if (ja == -1)
				ja += m;
			if (a[i + l / m][j + ja] < a[bst_i + l / m][bst_j + ja])
				bst_i = i,bst_j = j;
		}
	}

	for (int i=bst_i;i<bst_i + n;i++){
		for (int j=bst_j;j<bst_j + m;j++)
			cout<<a[i][j];
		cout<<'\n';
	}
}

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