oj.uz

Submission #1012567

# Submission time Handle Problem Language Result Execution time Memory
1012567 2024-07-02T10:53:54 Z Jawad_Akbar_JJ Sateliti (COCI20_satellti) C++17
10 / 110
 62 ms 6704 KB 
#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;
	if (j2 == j - 1)
		j2 += m;
	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 == m-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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 3 ms 2904 KB Output is correct
3 Correct 3 ms 3024 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 3080 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 3 ms 2904 KB Output is correct
3 Correct 3 ms 3024 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 3080 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 62 ms 6704 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Incorrect 3 ms 5980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 3 ms 2904 KB Output is correct
3 Correct 3 ms 3024 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 3080 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 62 ms 6704 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Incorrect 3 ms 5980 KB Output isn't correct
11 Halted 0 ms 0 KB -