제출 #1103829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103829		nrg_studio	Sateliti (COCI20_satellti)	C++17	10 / 110	53 ms	3656 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 = 2, b2 = 3;

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(2*n+1,1), exp2(2*m+1,1);
	F0R(i,2*n) {exp[i+1]=mul(exp[i],b);}
	F0R(i,2*m) {exp2[i+1]=mul(exp2[i],b2);}
	FOR(i,1,2*n+1) {
		FOR(j,1,2*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 ret = add(sub(sub(a[c1][d1],a[a1-1][d1]),a[c1][b1-1]),a[a1-1][b1-1]);
		//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;
	};
	auto cmp = [&](int a1, int b1, int c1, int d1, int a2, int b2, int c2, int d2)->bool {
		ll hsh = get(a1,b1,c1,d1), hsh2 = get(a2,b2,c2,d2);
		//cout<<hsh<<' '<<hsh2<<'\n';
		if (a2>a1) {hsh=mul(hsh,exp[a2-a1]);}
		else {hsh2=mul(hsh2,exp[a1-a2]);}
		if (b2>b1) {hsh=mul(hsh,exp2[b2-b1]);}
		else {hsh2=mul(hsh2,exp2[b1-b2]);}
		/*if (c1>c2) {mul(hsh2,exp[c1-c2]);}
		else {mul(hsh,exp[c2-c1]);}
		if (d1>d2) {mul(hsh2,exp2[d1-d2]);}
		else {mul(hsh,exp[d2-d1]);}*/
		return (hsh==hsh2);
	};
	//cout<<cmp(1,1,1,2,1,4,1,5);
	//return 0;
	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 (i==1&&j==4) {cout<<cmp(i+div,j,i+div,j+rem-1, r+div,c,r+div,c+rem-1)<<'\n';}
				if (div) {
					//flag &= (get(i,j,i+div-1,j+m-1)==get(r,c,r+div-1,c+m-1));
					flag &= cmp(i,j,i+div-1,j+m-1, 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));
					flag &= cmp(i+div,j,i+div,j+rem-1, 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';
	}
}

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