Submission #482509

#	Time	Username	Problem	Language	Result	Execution time	Memory
482509		mmonteiro	Sateliti (COCI20_satellti)	C++17	110 / 110	854 ms	37812 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 2000000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int normalize(int x)
{
	x = x % MOD;
	if(x < 0) x += MOD;
	return x;
}

int add(int a, int b)
{
	return normalize(normalize(a) + normalize(b));
}

int prod(int a, int b)
{
	return normalize(normalize(a) * normalize(b));
}

int sub(int a, int b)
{
	return normalize(normalize(a) - normalize(b));
}

int expMod(int x, int e)
{
	int ans = 1;
	while(e > 0)
	{
		if(e & 1LL) ans = prod(ans, x), e--;
		else x = prod(x, x), e /= 2;
	}
	return normalize(ans);
}

int inv(int x)
{
	return expMod(x, MOD - 2);
}

int n, m;
string image[2005];
int pf[2005][2005];
int P[2005];
int Q[2005];
int invpx[2005];
int invqx[2005];

int get(int i, int j) {
	int x = image[i - 1][j - 1] == '.' ? 1 : 0;
	return prod(x, prod(P[i], Q[j]));
}

void build() {
	P[0] = Q[0] = 1;
	for(int i = 1; i < 2005; i++) {
		P[i] = prod(17, P[i - 1]);
		Q[i] = prod(13, Q[i - 1]);
	}

	for(int i = 0; i < 2005; i++) {
		invqx[i] = inv( Q[i] );
		invpx[i] = inv( P[i] ); 
	}

	for(int i = 1; i <= 2 * n; i++)
		for(int j = 1; j <= 2 * m; j++)
			pf[i][j] = add(sub( add(pf[i - 1][j], pf[i][j - 1]), pf[i - 1][j - 1]), get(i, j));
}

int query(int i, int j) {
	return pf[i][j];
}

int sub_matrix(int x1, int y1, int x2, int y2) {
	int sum = 0;
	sum = add(sum, query(max(x1, x2), max(y1, y2)));
	sum = sub(sum, query(max(x1, x2), min(y1, y2) - 1));	
	sum = sub(sum, query(min(x1, x2) - 1, max(y1, y2)));
	sum = add(sum, query(min(x1, x2) - 1, min(y1, y2) - 1));

	sum = prod(sum, invpx[x1]);
	sum = prod(sum, invqx[y1]);

	return sum;	
}

int get_raw(int a, int b, int A, int B) {
	int l = 0, r = n - 1, ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2;
		int s1 = sub_matrix(a, b, a + mid, b + m - 1);
		int s2 = sub_matrix(A, B, A + mid, B + m - 1);
		if(s1 != s2) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	return ans;
}

int get_col(int a, int b, int A, int B, int R) {
	int l = 0, r = m - 1, ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2;
		int s1 = sub_matrix(a, b, a + R, b + mid);
		int s2 = sub_matrix(A, B, A + R, B + mid);
		if(s1 != s2) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	return ans;
}

void print_matrix(int I, int J) {
	I--; J--;
	for(int i = I; i < I + n; i++) {
		for(int j = J; j < J + m; j++)
			cout << image[i][j];
		cout << '\n';
	}	
}

void solve(){
   	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> image[i];
		image[i] += image[i];
		image[i + n] = image[i];
	}

	build();

	int I = 1, J = 1;
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= m; j++)
			if(image[i - 1][j - 1] == '*') 
				I = i, J = j, i = n, j = m;

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			int r = get_raw(i, j, I, J);
			if(r == -1) continue;
			int c = get_col(i, j, I, J, r);
			if(c == -1) continue;
		
			int pri = i + r - 1, prj = j + c - 1;
			if(image[pri][prj] == '*') I = i, J = j;
		}
	}
	
	print_matrix(I, J);

}

int32_t main() {
   fastio;
   int t = 1;
   for(int caso = 1; caso <= t; ++caso) {
      solve();
   }
   return 0;
}
/*
Before submit:
   Check the corners cases
   Check solution restrictions

For implementation solutions:
   Check the flow of the variables

For intervals problems:
   Think about two pointers

For complete search:
   Think about cuts

If you get WA:
   Reread your code looking for stupid typos
   Try various manual testcases 
   Recheck the correctness of your algorithm
   Reread the statement
   Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
   Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
   Change the coder (if you're with a team)
   Give up. You may have other tasks to solve.
*/

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