#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
constexpr int md = 1e9 + 9; constexpr int iv2 = (md + 1) / 2;
inline int add(int a, int b) { a += b; if(a>=md){a-=md;} return a; }
inline int sub(int a, int b) { a -= b; if(a<0){a+=md;} return a; }
inline int mul(int a, int b) { return (ll)a * b % md; }
inline int bp(int a, int n) { int res = 1;
for (; n; n >>= 1, a = mul(a, a)) {
if (n & 1) res = mul(res, a);
} return res;
}
inline int inv(int a) { return bp(a, md - 2); }
const int N = 2e6 + 10;
constexpr int p = 10039;
int pw[N], ipw[N];
inline void calc() {
const int ip = inv(p);
pw[0] = ipw[0] = 1;
for (int i = 1; i < N; ++i) {
pw[i] = mul(pw[i - 1], p);
ipw[i] = mul(ipw[i - 1], ip);
}
}
inline void solve() { calc();
int n, m;
cin >> n >> m;
ve<ve<char>> a(n,ve<char>(m));
for (auto &i : a) for (auto &j : i) cin >> j;
for (auto &i : a) for (auto &j : i) j = (j == '*' ? 'b' : 'c');
ve<ve<char>> c(2 * n, ve<char> (2 * m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
c[i][j] = a[i][j];
c[i + n][j] = a[i][j];
c[i][j + m] = a[i][j];
c[i + n][j + m] = a[i][j];
}
}
// cout << '\n';
// for (auto &i : c) {
// for (auto &j : i) cout << j;
// cout << '\n';
// }
// cout << '\n';
ve<ve<int>> ha(2 * n, ve<int> (2 * m));
for (int i = 0; i < 2 * n; ++i) {
ha[i][2 * m - 1] = (c[i][2 * m - 1] - 'a');
for (int j = 2 * m - 2; ~j; --j) {
ha[i][j] = add(mul(p, ha[i][j + 1]), c[i][j] - 'a');
}
}
ve<ve<int>> val(2 * n, ve<int> (m));
for (int i = 0; i < 2 * n; ++i) {
for (int j = 0; j < m; ++j) {
val[i][j] = sub(ha[i][j], mul(pw[m], ha[i][j + m]));
}
}
ve<ve<int>> tr(2 * n, ve<int> (m));
for (int j = 0; j < m; ++j) {
tr[2 * n - 1][j] = val[2 * n - 1][j];
for (int i = 2 * n - 2; ~i; --i) {
tr[i][j] = add(mul(pw[m], tr[i + 1][j]), val[i][j]);
}
}
auto get = [&](int x, int y, int len) {
int whole = len / m, r = len % m;
int hash = 0;
// [x, x + whole - 1]
hash = sub(tr[x][y], mul(pw[whole * m], tr[x + whole][y]));
int h = sub(ha[x + whole][y], mul(pw[r], ha[x + whole][y + r]));
hash = add(hash, mul(pw[whole * m], h) );
return hash;
};
auto compare = [&](int x1, int y1, int x2, int y2) {
int l = 1, r = n * m, mid, ans = 0;
while (l <= r) {
mid = l + r >> 1;
if (get(x1, y1, mid) == get(x2, y2, mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
if (ans == n * m) return 0;
else {
char A = c[x1 + (ans / m)][y1 + (ans % m)];
char B = c[x2 + (ans / m)][y2 + (ans % m)];
return (A < B ? -1 : 1);
}
};
int x = 0, y = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!i && !j) continue;
if (compare(i, j, x, y) == -1) tie(x, y) = mpp(i, j);
}
}
// cout << '\n' << '\n';
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << (c[x + i][y + j] == 'b' ? '*' : '.');
}
cout << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15976 KB |
Output is correct |
2 |
Correct |
17 ms |
16028 KB |
Output is correct |
3 |
Correct |
18 ms |
15976 KB |
Output is correct |
4 |
Correct |
18 ms |
16012 KB |
Output is correct |
5 |
Correct |
22 ms |
15988 KB |
Output is correct |
6 |
Correct |
21 ms |
15980 KB |
Output is correct |
7 |
Correct |
19 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15976 KB |
Output is correct |
2 |
Correct |
17 ms |
16028 KB |
Output is correct |
3 |
Correct |
18 ms |
15976 KB |
Output is correct |
4 |
Correct |
18 ms |
16012 KB |
Output is correct |
5 |
Correct |
22 ms |
15988 KB |
Output is correct |
6 |
Correct |
21 ms |
15980 KB |
Output is correct |
7 |
Correct |
19 ms |
16000 KB |
Output is correct |
8 |
Correct |
61 ms |
19296 KB |
Output is correct |
9 |
Correct |
21 ms |
16076 KB |
Output is correct |
10 |
Correct |
18 ms |
16100 KB |
Output is correct |
11 |
Correct |
60 ms |
19276 KB |
Output is correct |
12 |
Correct |
63 ms |
19356 KB |
Output is correct |
13 |
Correct |
63 ms |
19444 KB |
Output is correct |
14 |
Correct |
75 ms |
19412 KB |
Output is correct |
15 |
Correct |
63 ms |
19404 KB |
Output is correct |
16 |
Correct |
72 ms |
19412 KB |
Output is correct |
17 |
Correct |
65 ms |
19412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15976 KB |
Output is correct |
2 |
Correct |
17 ms |
16028 KB |
Output is correct |
3 |
Correct |
18 ms |
15976 KB |
Output is correct |
4 |
Correct |
18 ms |
16012 KB |
Output is correct |
5 |
Correct |
22 ms |
15988 KB |
Output is correct |
6 |
Correct |
21 ms |
15980 KB |
Output is correct |
7 |
Correct |
19 ms |
16000 KB |
Output is correct |
8 |
Correct |
61 ms |
19296 KB |
Output is correct |
9 |
Correct |
21 ms |
16076 KB |
Output is correct |
10 |
Correct |
18 ms |
16100 KB |
Output is correct |
11 |
Correct |
60 ms |
19276 KB |
Output is correct |
12 |
Correct |
63 ms |
19356 KB |
Output is correct |
13 |
Correct |
63 ms |
19444 KB |
Output is correct |
14 |
Correct |
75 ms |
19412 KB |
Output is correct |
15 |
Correct |
63 ms |
19404 KB |
Output is correct |
16 |
Correct |
72 ms |
19412 KB |
Output is correct |
17 |
Correct |
65 ms |
19412 KB |
Output is correct |
18 |
Correct |
648 ms |
54256 KB |
Output is correct |
19 |
Correct |
24 ms |
16604 KB |
Output is correct |
20 |
Correct |
26 ms |
16724 KB |
Output is correct |
21 |
Correct |
603 ms |
54396 KB |
Output is correct |
22 |
Correct |
685 ms |
54396 KB |
Output is correct |
23 |
Correct |
636 ms |
54404 KB |
Output is correct |
24 |
Correct |
684 ms |
54496 KB |
Output is correct |
25 |
Correct |
608 ms |
54468 KB |
Output is correct |
26 |
Correct |
698 ms |
54404 KB |
Output is correct |
27 |
Correct |
687 ms |
54332 KB |
Output is correct |