제출 #1103826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103826		nrg_studio	Sateliti (COCI20_satellti)	C++17	0 / 110	2 ms	336 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)

ll mod = 1e9+7;
ll b = 31, b2 = 37;

ll add(ll a, ll b) {return (a+b)%mod;}
ll sub(ll a, ll b) {return (a+mod-b)%mod;}
ll mul(ll a, ll b) {return (a*b)%mod;}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	char c1;
	// * is smaller than .
	vector<vector<ll>> a(2*n+1,vector<ll>(2*m+1,0));
	vector<vector<char>> o(2*n+1,vector<char>(2*m+1));
	FOR(i,1,n+1) {
		FOR(j,1,m+1) {
			cin >> c1; 
			a[i][j] = a[i+n][j] = a[i][j+m] = a[i+n][j+m] = (c1=='.')+1;
			o[i][j] = o[i+n][j] = o[i][j+m] = o[i+n][j+m] = c1;
		}
	}
	int r = 1, c = 1;
	vector<ll> exp(n+1,1), exp2(m+1,1);
	F0R(i,n) {exp[i+1]=mul(exp[i],b);}
	F0R(i,m) {exp2[i+1]=mul(exp2[i],b2);}
	FOR(i,1,n+1) {
		FOR(j,1,m+1) {
			a[i][j] = mul(a[i][j],mul(exp[i],exp2[j]));
			a[i][j] = sub(add(add(a[i][j],a[i-1][j]),a[i][j-1]),a[i-1][j-1]);
		}
	}
	auto get = [&](int a1, int b1, int c1, int d1)->ll {
		ll q1 = mul(a[a1-1][d1],exp[c1-a1+1]);
		ll q3 = mul(a[c1][b1-1],exp2[d1-b1+1]);
		ll q2 = mul(a[a1-1][b1-1],mul(exp[c1-a1+1],exp2[d1-b1+1]));
		ll ret = add(sub(sub(a[c1][d1],q1),q3),q2);
		return ret;
	};
	FOR(i,1,n+1) {
		FOR(j,1,m+1) {
			int l = 1, h = n*m, mid = (l+h)/2;
			int work = 0;
			while (l <= h) {
				int flag = 1;
				int div = mid/m, rem = mid%m;
				if (div) {flag &= (get(i,j,i+div-1,j+m-1)==get(r,c,r+div-1,c+m-1));}
				if (rem) {flag &= (get(i+div,j,i+div,j+rem-1)==get(r+div,c,r+div,c+rem-1));}
				
				if (flag) {l = mid+1; work = mid;}
				else {h = mid-1;}
				mid = (l+h)/2;
			}
			if (work != n*m) {
				work++;
				if (o[i+work/m][j+work%m-1]<o[r+work/m][c+work%m-1]) {r = i; c = j;}
			}
			// side cases: nothing works, everything works (only have to consider second one)
		}
	}
	F0R(i,n) {
		F0R(j,m) {cout << o[i+r][j+c];} cout << '\n';
	}
	//cout << get(1,1,2,2) << '\n';
	//cout << get(2,2,3,3) << '\n';
}

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