oj.uz

Submission #482509

# Submission time Handle Problem Language Result Execution time Memory
482509 2021-10-25T06:23:01 Z mmonteiro Sateliti (COCI20_satellti) C++17
110 / 110
 854 ms 37812 KB 
#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.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 948 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 59 ms 5864 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 59 ms 5860 KB Output is correct
12 Correct 65 ms 5928 KB Output is correct
13 Correct 66 ms 6036 KB Output is correct
14 Correct 78 ms 6036 KB Output is correct
15 Correct 60 ms 6040 KB Output is correct
16 Correct 74 ms 6048 KB Output is correct
17 Correct 66 ms 6036 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 948 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 59 ms 5864 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 59 ms 5860 KB Output is correct
12 Correct 65 ms 5928 KB Output is correct
13 Correct 66 ms 6036 KB Output is correct
14 Correct 78 ms 6036 KB Output is correct
15 Correct 60 ms 6040 KB Output is correct
16 Correct 74 ms 6048 KB Output is correct
17 Correct 66 ms 6036 KB Output is correct
18 Correct 751 ms 36708 KB Output is correct
19 Correct 14 ms 8864 KB Output is correct
20 Correct 13 ms 1100 KB Output is correct
21 Correct 740 ms 37748 KB Output is correct
22 Correct 830 ms 37812 KB Output is correct
23 Correct 725 ms 37744 KB Output is correct
24 Correct 833 ms 37740 KB Output is correct
25 Correct 708 ms 37756 KB Output is correct
26 Correct 821 ms 37744 KB Output is correct
27 Correct 854 ms 37716 KB Output is correct