oj.uz

답안 #482508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482508 2021-10-25T06:15:36 Z mmonteiro Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 36692 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 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 = 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, inv(P[x1]));
	sum = prod(sum, inv(Q[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;
	
	// int s1 = sub_matrix(a, b, a + R, b + 1);
	// int s2 = sub_matrix(A, B, A + R, B + 1);
	
	// bug(a _ b _ A _ B _ "oi" _ s1 _ s2);
	
	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;
		
		// bug(A _ A + R _ s1 _ s2);
	}
	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();

	// cout << get_raw(1, 2, 2, 1) << '\n';
	// cout << get_col(1, 2, 2, 1, 0) << '\n';


	// for(int i = 1; i <= 2 * n; i++)  {
	// 	for(int j = 1; j <= 2 * m; j++)
	// 		cout << pf[i][j] << ' ';
	// 	cout << endl;
	// }

	// // cout << get_raw(1, 1, 1, 1) << '\n';

	// // return;

	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;

	// bug(I _ J);

	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;
			// bug(pri _ prj);

			// print_matrix(I, J);

			// cout << endl;

			// print_matrix(i, j);

			// cout << endl;
			// cout << endl;

			if(image[pri][prj] == '*') I = i, J = j;

		}
	}
	
	// bug(I _ J);
	print_matrix(I, J);

}

int32_t main() {
   fastio;
   int t = 1;
   //cin >> t;
   for(int caso = 1; caso <= t; ++caso) {
      //cout << "Case #" << 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

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 844 KB Output is correct
2 Correct 26 ms 844 KB Output is correct
3 Correct 27 ms 844 KB Output is correct
4 Correct 15 ms 844 KB Output is correct
5 Correct 25 ms 844 KB Output is correct
6 Correct 24 ms 844 KB Output is correct
7 Correct 16 ms 916 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 844 KB Output is correct
2 Correct 26 ms 844 KB Output is correct
3 Correct 27 ms 844 KB Output is correct
4 Correct 15 ms 844 KB Output is correct
5 Correct 25 ms 844 KB Output is correct
6 Correct 24 ms 844 KB Output is correct
7 Correct 16 ms 916 KB Output is correct
8 Correct 1464 ms 5908 KB Output is correct
9 Correct 35 ms 588 KB Output is correct
10 Correct 5 ms 2764 KB Output is correct
11 Correct 1476 ms 5908 KB Output is correct
12 Correct 1526 ms 5984 KB Output is correct
13 Correct 1530 ms 6108 KB Output is correct
14 Correct 1568 ms 6104 KB Output is correct
15 Correct 1519 ms 6104 KB Output is correct
16 Correct 1538 ms 6156 KB Output is correct
17 Correct 1581 ms 6100 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 844 KB Output is correct
2 Correct 26 ms 844 KB Output is correct
3 Correct 27 ms 844 KB Output is correct
4 Correct 15 ms 844 KB Output is correct
5 Correct 25 ms 844 KB Output is correct
6 Correct 24 ms 844 KB Output is correct
7 Correct 16 ms 916 KB Output is correct
8 Correct 1464 ms 5908 KB Output is correct
9 Correct 35 ms 588 KB Output is correct
10 Correct 5 ms 2764 KB Output is correct
11 Correct 1476 ms 5908 KB Output is correct
12 Correct 1526 ms 5984 KB Output is correct
13 Correct 1530 ms 6108 KB Output is correct
14 Correct 1568 ms 6104 KB Output is correct
15 Correct 1519 ms 6104 KB Output is correct
16 Correct 1538 ms 6156 KB Output is correct
17 Correct 1581 ms 6100 KB Output is correct
18 Execution timed out 3097 ms 36692 KB Time limit exceeded
19 Halted 0 ms 0 KB -