oj.uz

Submission #589482

# Submission time Handle Problem Language Result Execution time Memory
589482 2022-07-04T18:56:21 Z penguinhacker Sateliti (COCI20_satellti) C++17
110 / 110
 1133 ms 69068 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

template<class A, size_t sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
	out << '[';
	for (int i = 0; i < sz; ++i) {
		if (i > 0) out << ", ";
		out << a[i];
	}
	return out << ']';
}

// '*'<'.'

const int M=1e9+696969;

ar<int, 2> operator+(ar<int, 2> a, ar<int, 2> b) {
	ar<int, 2> c;
	for (int i : {0, 1})
		if ((c[i]=a[i]+b[i])>=M)
			c[i]-=M;
	return c;
}
 
ar<int, 2> operator-(ar<int, 2> a, ar<int, 2> b) {
	ar<int, 2> c;
	for (int i : {0, 1})
		if ((c[i]=a[i]-b[i])<0)
			c[i]+=M;
	return c;
}
 
ar<int, 2> operator*(ar<int, 2> a, ar<int, 2> b) {
	return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
}

ar<int, 2> mk(char c) {
	return {c, c};
}

const ar<int, 2> B1={343247, 34012321}, B2={6961231, 7231398};
int n, m;
ar<int, 2> a[2001][2001], b[2000][2001], p1[2000], p2[2000];
string s[2000];

ar<int, 2> 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])*p1[n-i-1]*p2[m-j-1];
}

ar<int, 2> Get2(int i, int j, int dj) {
	return (b[i][j+dj]-b[i][j])*p2[m-j-1];
}

void solve() {
	p1[0]=p2[0]={1, 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];
	for (int i=1; i<2*m; ++i)
		p2[i]=B2*p2[i-1];
	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]+mk(s[i][j])*p1[i]*p2[j];
	for (int i=0; i<2*n; ++i)
		for (int j=0; j<2*m; ++j)
			b[i][j+1]=b[i][j]+mk(s[i][j])*p2[j];
	ar<int, 2> ans={0, 0};
	//cout << b[0][3] << " " << b[0][2] << " " << Get2(0, 2, 1) << endl;
	//exit(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))
				continue;
			int l=1, r=n;
			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;
			//cout << j << " " << ans[1] << " " << dj << endl;
			//if (j==2) cout << Get2(0, 1, 1) << " " << Get2(0, 2, 1) << 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";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}

Compilation message

Main.cpp: In function 'std::array<int, 2> operator*(std::array<int, 2>, std::array<int, 2>)':
Main.cpp:37:23: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](0)) * ((long long int)b.std::array<int, 2>::operator[](0))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
   37 |  return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
      |          ~~~~~~~~~~~~~^~
Main.cpp:37:40: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](1)) * ((long long int)b.std::array<int, 2>::operator[](1))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
   37 |  return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
      |                           ~~~~~~~~~~~~~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 1156 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 82 ms 10944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 80 ms 10948 KB Output is correct
12 Correct 85 ms 11148 KB Output is correct
13 Correct 86 ms 11308 KB Output is correct
14 Correct 91 ms 11300 KB Output is correct
15 Correct 85 ms 11300 KB Output is correct
16 Correct 89 ms 11340 KB Output is correct
17 Correct 88 ms 11372 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 1156 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 82 ms 10944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 80 ms 10948 KB Output is correct
12 Correct 85 ms 11148 KB Output is correct
13 Correct 86 ms 11308 KB Output is correct
14 Correct 91 ms 11300 KB Output is correct
15 Correct 85 ms 11300 KB Output is correct
16 Correct 89 ms 11340 KB Output is correct
17 Correct 88 ms 11372 KB Output is correct
18 Correct 1020 ms 68900 KB Output is correct
19 Correct 20 ms 17108 KB Output is correct
20 Correct 15 ms 1712 KB Output is correct
21 Correct 1010 ms 68968 KB Output is correct
22 Correct 1094 ms 68972 KB Output is correct
23 Correct 990 ms 68996 KB Output is correct
24 Correct 1133 ms 69068 KB Output is correct
25 Correct 994 ms 68972 KB Output is correct
26 Correct 1120 ms 68972 KB Output is correct
27 Correct 1101 ms 68904 KB Output is correct