Submission #589482

#	Time	Username	Problem	Language	Result	Execution time	Memory
589482		penguinhacker	Sateliti (COCI20_satellti)	C++17	110 / 110	1133 ms	69068 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60