#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define N 2051
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
//#define endl '\n'
#define _ << " " <<
#define F first
#define S second
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;
bitset <N> bt[N], lt, rt;
ll pw[N][2], pr[N][N];
ll mlt(ll x, ll y)
{
return (x * y) % M;
}
ll sm(ll x, ll y)
{
x += y;
if (x >= M)
x -= M;
return x;
}
ll sub(ll x, ll y)
{
x -= y;
if (x < 0)
x += M;
return x;
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
pw[0][0] = 1;
for (int i = 1; i < N; i++)
pw[i][0] = mlt(pw[i - 1][0], 2);
pw[0][1] = 1;
for (int i = 1; i < N; i++)
pw[i][1] = mlt(pw[i - 1][1], 3);
int n, m;
cin >> n >> m;
string s[n + n];
for (int i = 0; i < n; i++)
cin >> s[i];
for (int i = 0; i < n; i++)
{
s[i] = s[i] + s[i];
s[i + n] = s[i];
}
int a[n + n][m + m];
for (int i = 0; i < n + n; i++)
for (int j = 0; j < m + m; j++)
{
if (s[i][j] == '*')
{
a[i][j] = 1;
bt[i][j] = 1;
}
else a[i][j] = 0;
}
for (int i = 0; i < n + n; i++)
for (int j = 0; j < m + m; j++)
{
pr[i][j] = mlt(mlt(pw[j][0], pw[i][1]), a[i][j]);
if (i != 0)
pr[i][j] = sm(pr[i][j], pr[i - 1][j]);
if (j != 0)
pr[i][j] = sm(pr[i][j], pr[i][j - 1]);
if (i != 0 && j != 0)
pr[i][j] = sub(pr[i][j], pr[i - 1][j - 1]);
}
int x = 0, y = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (i + j == 0) continue;
int l = 0, r = m - 1;
while (l < r)
{
int md = (l + r) >> 1;
bool ft = 1;
ll h = pr[i + md][j + m];
if (i != 0)
h = sub(h, pr[i - 1][j + m]);
if (j != 0)
h = sub(h, pr[i + md][j - 1]);
if (i != 0 && j != 0)
h = sm(h, pr[i - 1][j - 1]);
if (x > i)
h = mlt(h, pw[x - i][1]);
if (y > j)
h = mlt(h, pw[y - j][0]);
ll p = pr[x + md][y + m];
if (x != 0)
p = sub(p, pr[x - 1][y + m]);
if (y != 0)
p = sub(p, pr[x + md][y - 1]);
if (x != 0 && y != 0)
p = sm(p, pr[x - 1][y - 1]);
if (x < i)
p = mlt(p, pw[i - x][1]);
if (y < j)
p = mlt(p, pw[j - y][0]);
ft = (p == h);
if (ft)
l = md + 1;
else r = md;
}
lt = bt[x + l];
rt = bt[i + l];
lt >>= y;
rt >>= j;
int ps = (lt ^ rt)._Find_first();
int t = 0;
while (t + y < m + m && t + j < m + m && a[x + l][t + y] == a[i + l][t + j])
t++;
if (ps < m || t < m)
assert(t == ps);
if (ps < m && lt[ps] == 0)
{
x = i; y = j;
}
}
for (int i = x; i < x + n; i++)
{
for (int j = y; j < y + m; j++)
cout << s[i][j];
cout << endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:150:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
150 | if (y > j)
| ^~
Main.cpp:153:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
153 | ll p = pr[x + md][y + m];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
896 KB |
Output is correct |
| 8 |
Correct |
41 ms |
7404 KB |
Output is correct |
| 9 |
Runtime error |
4 ms |
1004 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
2 ms |
876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
896 KB |
Output is correct |
| 8 |
Correct |
41 ms |
7404 KB |
Output is correct |
| 9 |
Runtime error |
4 ms |
1004 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
