#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
//#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 2005;
int pr[N][N];
int invi[N * N], invj[N * N], pwi[N * N], pwj[N * N];
char c;
int a[N][N];
int n, m, I, J;
int mult(ll x, ll y) {return (x * y) % M;}
int sum(int x, int y) {x += y; if (x >= M) x -= M; return x;}
int mi(int x, int y) {x -= y; if (x < 0) x += M; return x;}
int bp(int x, int y) {
if (!y) {
return 1;
}
if (y & 1) {
return mult(x, bp(x, y - 1));
}
int a = bp(x, y >> 1);
return mult(a, a);
}
int get(int il, int jl, int ir, int jr) {
// cerr << sum(mi(mi(pr[ir][jr], pr[il - 1][jr]), pr[ir][jl - 1]), pr[il - 1][jl - 1]) << el;
return mult(invi[il - 1], mult(invj[jl - 1], sum(mi(mi(pr[ir][jr], pr[il - 1][jr]), pr[ir][jl - 1]), pr[il - 1][jl - 1])));
}
void upd(int i, int j) {
int l = 1, r = n;
while (l < r) {
int md = (l + r + 1) >> 1;
if (get(i, j, i + md - 1, j + m - 1) == get(I, J, I + md - 1, J + m - 1)) {
l = md;
}
else {
r = md - 1;
}
}
int L = r;
if (a[i + L - 1][j] != a[I + L - 1][J]) {
if (a[i + L - 1][j] < a[I + L - 1][J]) {
I = i;
J = j;
}
}
l = 1;
r = m;
while (l < r) {
int md = (l + r + 1) >> 1;
if (get(i + L - 1, j, i + L - 1, j + md - 1) == get(I + L - 1, J, I + L - 1, J + md - 1)) {
l = md;
}
else {
r = md - 1;
}
}
assert(r < m);
if (a[i + L - 1][j + r] < a[I + L - 1][J + r]) {
I = i;
J = j;
}
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n >> m;
pwi[0] = pwj[0] = 1;
invi[0] = invj[0] = 1;
for (int i = 1; i <= 4 * n * m; i++) {
pwi[i] = mult(pwi[i - 1], 7);
invi[i] = bp(pwi[i], M - 2);
pwj[i] = mult(pwj[i - 1], 11);
invj[i] = bp(pwj[i], M - 2);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
a[i][j] = (c == '.');
}
}
for (int i = n + 1; i <= 2 * n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = a[i - n][j];
}
for (int j = m + 1; j <= 2 * m; j++) {
a[i][j] = a[i - n][j - m];
}
}
for (int i = 1; i <= n; i++) {
for (int j = m + 1; j <= 2 * m; j++) {
a[i][j] = a[i][j - m];
}
}
for (int i = 1; i <= 2 * n; i++) {
for (int j = 1; j <= 2 * m; j++) {
pr[i][j] = sum(mi(sum(pr[i - 1][j], pr[i][j - 1]), pr[i - 1][j - 1]), mult(pwi[i - 1], mult(pwj[j - 1], a[i][j] + 1)));
}
}
I = 1;
J = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) {
continue;
}
upd(i, j);
}
}
for (int i = I; i <= I + n - 1; i++, cout << el) {
for (int j = J; j <= J + m - 1; j++) {
if (a[i][j]) {
cout << '.';
}
else {
cout << '*';
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
2796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
2796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
2796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
