oj.uz

Submission #527992

# Submission time Handle Problem Language Result Execution time Memory
527992 2022-02-19T01:07:05 Z penguinhacker Sateliti (COCI20_satellti) C++14
10 / 110
 25 ms 10952 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

// '*'<'.'

const int B1=2394, B2=696961, M=1e9+7;
int n, m;
ll a[2001][2001], b[2000][2001], p1[2000], p2[2000];
string s[2000];

ll Get(int i, int j, int di, int dj) {
	return (a[i+di][j+dj]-a[i+di][j]-a[i][j+dj]+a[i][j]+2*M)*p1[n-i-1]%M*p2[m-j-1]%M;
}

ll Get2(int i, int j, int dj) {
	return (b[i][j+dj]-b[i][j]+M)*p1[m-j-1]%M;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	p1[0]=p2[0]=1;
	cin >> n >> m;
	for (int i=0; i<n; ++i) {
		cin >> s[i];
		s[i]+=s[i];
		s[n+i]=s[i];
	}
	for (int i=1; i<2*n; ++i)
		p1[i]=B1*p1[i-1]%M;
	for (int i=1; i<2*m; ++i)
		p2[i]=B2*p2[i-1]%M;
	for (int i=0; i<2*n; ++i)
		for (int j=0; j<2*m; ++j)
			a[i+1][j+1]=(a[i+1][j]+a[i][j+1]-a[i][j]+M+(s[i][j]=='*'?0:p1[i]*p2[j]))%M;
	for (int i=0; i<2*n; ++i)
		for (int j=0; j<2*m; ++j)
			b[i][j+1]=(b[i][j]+(s[i][j]=='*'?0:p1[j]))%M;
	//cout << Get(2, 1, 1, 2)/36 << endl;
	ar<int, 2> ans={0, 0};
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j) {
			if (!i&&!j)
				continue;
			if (Get(i, j, n, m)==Get(ans[0], ans[1], n, m)) {
				//cout << i << " " << j << " " << Get(i, j, n, m) << " " << Get(ans[0], ans[1], n, m) << endl;
				continue;
			}
			int l=1, r=n-1;
			while(l<r) {
				int mid=(l+r)/2;
				if (Get(i, j, mid, m)!=Get(ans[0], ans[1], mid, m))
					r=mid;
				else
					l=mid+1;
			}
			int di=l-1;
			l=1, r=m;
			while(l<r) {
				int mid=(l+r)/2;
				if (Get2(i+di, j, mid)!=Get2(ans[0]+di, ans[1], mid))
					r=mid;
				else
					l=mid+1;
			}
			int dj=l-1;
			//if (i==0&&j==1)
			//	cout << di << " " << dj << endl;
			assert(s[i+di][j+dj]!=s[ans[0]+di][ans[1]+dj]);
			if (s[i+di][j+dj]<s[ans[0]+di][ans[1]+dj])
				ans={i, j};
		}
	for (int i=0; i<n; ++i)
		cout << s[i+ans[0]].substr(ans[1], m) << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1360 KB Output is correct
2 Correct 2 ms 1232 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 1 ms 1232 KB Output is correct
7 Correct 1 ms 1360 KB Output is correct
8 Correct 25 ms 10952 KB Output is correct
9 Runtime error 3 ms 1352 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1360 KB Output is correct
2 Correct 2 ms 1232 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 1 ms 1232 KB Output is correct
7 Correct 1 ms 1360 KB Output is correct
8 Correct 25 ms 10952 KB Output is correct
9 Runtime error 3 ms 1352 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -