#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
int n, m;
const int N = 1e3 + 5;
const int NN = 2e3 + 5;
bool s[NN][NN];
int h[NN][NN], pw[NN], mpw[NN], PW[NN][NN], x, y;
int subh(int i, int j, int n, int m) {
using namespace MD;
int res = h[i + n][j + m];
sub(res, h[i][j + m]);
sub(res, h[i + n][j]);
add(res, h[i][j]);
return prod(res, PW[i][j]);
}
void upd(int i, int j) {
if(subh(i, j, n, m) == subh(x, y, n, m)) return;
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;
subh(x, y, mid + 1, m) ==
subh(i, j, mid + 1, m)
? l = mid + 1
: r = mid;
}
int I = l;
l = 0, r = m - 1;
while(l < r) {
int mid = l + r >> 1;
subh(x, y, I + 1, mid + 1) ==
subh(i, j, I + 1, mid + 1)
? l = mid + 1
: r = mid;
}
int J = l;
for(int pi = 0; pi < I; ++pi)
for(int pj = 0; pj < m; ++pj)
assert(s[i + pi][j + pj] == s[x + pi][y + pj]);
for(int pj = 0; pj < J; ++pj)
assert(s[i + I][j + pj] == s[x + I][y + pj]);
assert(s[i + I][j + J] != s[x + I][y + J]);
if(s[i + I][j + J] < s[x + I][y + J])
x = i, y = j;
}
void solve() {
using namespace MD;
cin >> n >> m;
for(int i = 0; i < NN; ++i)
pw[i] = i ? prod(pw[i - 1], 2) : 1;
for(int i = 0; i < NN; ++i)
mpw[i] = i ? prod(mpw[i - 1], pw[m]) : 1;
for(int i = 0; i < NN - 1; ++i)
for(int j = 0; j < NN - 1; ++j)
PW[i][j] = prod(pw[NN - 1 - j], mpw[NN - 1 - i]);
for(int i = 0; i < n + n; ++i) {
for(int j = 0; j < m + m; ++j) {
if(i < n && j < m) {
char c; cin >> c;
s[i][j] = c == '.';
} else s[i][j] = s[i % n][j % m];
h[i + 1][j + 1] = prod(pw[j], prod(s[i][j], mpw[i]));
add(h[i + 1][j + 1], h[i][j + 1]);
add(h[i + 1][j + 1], h[i + 1][j]);
sub(h[i + 1][j + 1], h[i][j]);
}
}
x = y = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(i || j) upd(i, j);
for(int i = 0; i < n; ++i, cout << '\n')
for(int j = 0; j < m; ++j)
cout << (s[i + x][j + y] ? '.' : '*');
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
Main.cpp: In function 'void upd(int, int)':
Main.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = l + r >> 1;
| ~~^~~
Main.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 4 |
Correct |
16 ms |
16620 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 6 |
Correct |
19 ms |
16780 KB |
Output is correct |
| 7 |
Correct |
20 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 4 |
Correct |
16 ms |
16620 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 6 |
Correct |
19 ms |
16780 KB |
Output is correct |
| 7 |
Correct |
20 ms |
16748 KB |
Output is correct |
| 8 |
Correct |
78 ms |
20972 KB |
Output is correct |
| 9 |
Correct |
17 ms |
16236 KB |
Output is correct |
| 10 |
Correct |
18 ms |
19692 KB |
Output is correct |
| 11 |
Correct |
66 ms |
20972 KB |
Output is correct |
| 12 |
Correct |
484 ms |
21100 KB |
Output is correct |
| 13 |
Correct |
74 ms |
21228 KB |
Output is correct |
| 14 |
Correct |
143 ms |
21228 KB |
Output is correct |
| 15 |
Correct |
65 ms |
21228 KB |
Output is correct |
| 16 |
Correct |
82 ms |
21228 KB |
Output is correct |
| 17 |
Correct |
673 ms |
21144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16620 KB |
Output is correct |
| 4 |
Correct |
16 ms |
16620 KB |
Output is correct |
| 5 |
Correct |
17 ms |
16748 KB |
Output is correct |
| 6 |
Correct |
19 ms |
16780 KB |
Output is correct |
| 7 |
Correct |
20 ms |
16748 KB |
Output is correct |
| 8 |
Correct |
78 ms |
20972 KB |
Output is correct |
| 9 |
Correct |
17 ms |
16236 KB |
Output is correct |
| 10 |
Correct |
18 ms |
19692 KB |
Output is correct |
| 11 |
Correct |
66 ms |
20972 KB |
Output is correct |
| 12 |
Correct |
484 ms |
21100 KB |
Output is correct |
| 13 |
Correct |
74 ms |
21228 KB |
Output is correct |
| 14 |
Correct |
143 ms |
21228 KB |
Output is correct |
| 15 |
Correct |
65 ms |
21228 KB |
Output is correct |
| 16 |
Correct |
82 ms |
21228 KB |
Output is correct |
| 17 |
Correct |
673 ms |
21144 KB |
Output is correct |
| 18 |
Correct |
584 ms |
36652 KB |
Output is correct |
| 19 |
Correct |
27 ms |
28268 KB |
Output is correct |
| 20 |
Correct |
25 ms |
16492 KB |
Output is correct |
| 21 |
Correct |
753 ms |
36872 KB |
Output is correct |
| 22 |
Execution timed out |
3040 ms |
35692 KB |
Time limit exceeded |
| 23 |
Halted |
0 ms |
0 KB |
- |
