#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>
// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;
using namespace std;
const int LARGE = 1e9;
#define all(x) (x).begin(), (x).end()
using ll = long long;
typedef pair<ll, ll> pi;
// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
// if (a.second < b.second)
// return true;
// return false;
// }
// struct node
// {
// // part which will store data
// int data;
// // pointer to the previous node
// struct node *prev;
// // pointer to the next node
// struct node *next;
// };
// struct trienode
// {
// vector<trienode*> desc;
// vector<ll> descExist;
// trienode(ll M) {
// desc.resize(M);
// descExist.resize(M);
// }
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// static const int mod = MOD;
// static constexpr mint rt() { return RT; } // primitive root
// int v;
// explicit operator int() const { return v; }
// mint():v(0) {}
// mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// mint& operator+=(mint o) {
// if ((v += o.v) >= MOD) v -= MOD;
// return *this; }
// mint& operator-=(mint o) {
// if ((v -= o.v) < 0) v += MOD;
// return *this; }
// mint& operator*=(mint o) {
// v = int((ll)v*o.v%MOD); return *this; }
// friend mint pow(mint a, ll p) { assert(p >= 0);
// return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// friend mint operator+(mint a, mint b) { return a += b; }
// friend mint operator-(mint a, mint b) { return a -= b; }
// friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;
struct mySeg
{
vector<ll> A;
ll N;
void build()
{
A.resize(N * 2);
for (int i = 0; i < N; i++)
A[i + N] = A[i];
for (int i = N - 1; i > 0; i--)
A[i] = min(A[i << 1], A[i << 1 ^ 1]);
// for (auto el : A) cout << el << " ";
}
void set(ll idx, ll val)
{
idx += N;
A[idx] = val;
for (int i = idx >> 1; i > 0; i >>= 1)
A[i] = min(A[i << 1], A[i << 1 ^ 1]);
// for (auto el : A) cout << el << " ";
}
ll minnQuery(ll l, ll r)
{
ll minn = INT64_MAX;
for (l = l + N, r = r + N; l < r; l >>= 1, r >>= 1)
{
if (l % 2)
minn = min(minn, A[l++]);
if (r % 2)
minn = min(minn, A[--r]);
}
return minn;
}
};
// template <class T>
// class myFen
// {
// private:
// int N;
// vector<T> A;
// vector<T> BIT;
// public:
// myFen(int size) : N(size), A(size + 1), BIT(size + 1) {}
// void set(ll idx, ll val)
// {
// update(idx, val - A[idx]);
// A[idx] = val;
// }
// void update(ll idx, ll diff)
// {
// for (idx = idx; idx <= N; idx += idx & (-idx))
// BIT[idx] += diff;
// }
// ll sumQuery(ll idx)
// {
// if (idx == 0)
// return 0LL;
// ll summ = 0;
// for (idx = idx; idx > 0; idx -= idx & (-idx))
// summ += BIT[idx];
// return summ;
// }
// };
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
// class HashedString {
// private:
// // change M and B if you want
// static const ll M = (1LL << 61) - 1;
// static const ll B;
// // pow[i] contains B^i % M
// static vector<ll> pow;
// // p_hash[i] is the hash of the first i characters of the given string
// vector<ll> p_hash;
// __int128 mul(ll a, ll b) { return (__int128)a * b; }
// ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
// public:
// HashedString(const string &s) : p_hash(s.size() + 1) {
// while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
// p_hash[0] = 0;
// for (int i = 0; i < s.size(); i++) {
// p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
// }
// }
// ll get_hash(int start, int end) {
// ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
// return (raw_val + M) % M;
// }
// };
// mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// vector<ll> HashedString::pow = {1};
// const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
ll power(ll x, ll y, ll M)
{
if (y == 0)
return ll(1);
ll p = power(x, y / ll(2), M) % M;
p = (p * p) % M;
return (y % ll(2) == 0) ? p : (x * p) % M;
}
ll solve()
{
ll N, M; cin >> N >> M;
vector<vector<ll>> A(N*2, vector<ll>(0));
for (int i = 0; i < N; i++) {
string S; cin >> S;
for (int j = 0; j < M; j++) {
if (S[j] == '.') A[i].push_back(1);
else A[i].push_back(0);
}
for (int j = 0; j < M; j++) {
A[i].push_back(A[i][j]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M*2; j++) {
A[N+i].push_back(A[i][j]);
}
}
N *= 2, M *= 2;
vector<vector<ll>> PSHASH1(N+1, vector<ll>(M+1));
vector<vector<ll>> PSHASH1ROW(N+1, vector<ll>(M+1));
vector<vector<ll>> PSHASH2(N+1, vector<ll>(M+1));
vector<vector<ll>> PSHASH2ROW(N+1, vector<ll>(M+1));
ll MOD = (1LL<<61)-1;
ll p1 = 2, p2 = 5, q1 = 3, q2 = 7;
vector<ll> powp1(N+1);vector<ll> powp2(N+1);vector<ll> powq1(M+1);vector<ll> powq2(M+1);
powp1[0] = powp2[0] = powq1[0] = powq2[0] = 1;
for (int i = 1; i <= N; i++) {
powp1[i] = (__int128)powp1[i-1]*p1%MOD;
powp2[i] = (__int128)powp2[i-1]*p2%MOD;
}
for (int j = 1; j <= M; j++) {
powq1[j] = (__int128)powq1[j-1]*q1%MOD;
powq2[j] = (__int128)powq2[j-1]*q2%MOD;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
ll hash1 = (__int128)A[i-1][j-1]*powp1[i-1]*powq1[j-1]%MOD;
ll hash2 = (__int128)A[i-1][j-1]*powp2[i-1]*powq2[j-1]%MOD;
PSHASH1[i][j] = (PSHASH1[i-1][j]+PSHASH1[i][j-1]-PSHASH1[i-1][j-1]+hash1)%MOD;
PSHASH2[i][j] = (PSHASH2[i-1][j]+PSHASH2[i][j-1]-PSHASH2[i-1][j-1]+hash2)%MOD;
PSHASH1ROW[i][j] = (PSHASH1ROW[i][j-1]+hash1)%MOD;
PSHASH2ROW[i][j] = (PSHASH2ROW[i][j-1]+hash2)%MOD;
}
}
ll bestI = 1, bestJ = 1;
for (int i = 1; i <= N/2; i++) {
for (int j = 1; j <= M/2; j++) {
if (i == 1 && j == 1) continue;
ll l = 1, r = N/2*M/2;
while (l <= r) {
ll m = l+(r-l)/2;
ll rowCnt = m/(M/2)+(m%(M/2)==0?-1:0);
ll remm = m%(M/2);
if (remm == 0) remm = M/2;
ll x1 = bestI+rowCnt, y1 = bestJ+(M/2)-1;
ll x2 = i+rowCnt, y2 = j+(M/2)-1;
ll besthash1 = (((__int128)PSHASH1[x1][y1]-PSHASH1[x1][bestJ-1]-PSHASH1[bestI-1][y1]+PSHASH1[bestI-1][bestJ-1]-(PSHASH1ROW[x1][y1]-PSHASH1ROW[x1][bestJ+remm-1]))+MOD)%MOD;
ll besthash2 = (((__int128)PSHASH2[x1][y1]-PSHASH2[x1][bestJ-1]-PSHASH2[bestI-1][y1]+PSHASH2[bestI-1][bestJ-1]-(PSHASH2ROW[x1][y1]-PSHASH2ROW[x1][bestJ+remm-1]))+MOD)%MOD;
ll currhash1 = (((__int128)PSHASH1[x2][y2]-PSHASH1[x2][j-1]-PSHASH1[i-1][y2]+PSHASH1[i-1][j-1]-(PSHASH1ROW[x2][y2]-PSHASH1ROW[x2][j+remm-1]))+MOD)%MOD;
ll currhash2 = (((__int128)PSHASH2[x2][y2]-PSHASH2[x2][j-1]-PSHASH2[i-1][y2]+PSHASH2[i-1][j-1]-(PSHASH2ROW[x2][y2]-PSHASH2ROW[x2][j+remm-1]))+MOD)%MOD;
if (bestI < i) {
besthash1 = (__int128)besthash1*powp1[i-bestI]%MOD;
besthash2 = (__int128)besthash2*powp2[i-bestI]%MOD;
} else {
currhash1 = (__int128)currhash1*powp1[bestI-i]%MOD;
currhash2 = (__int128)currhash2*powp2[bestI-i]%MOD;
}
if (bestJ < j) {
besthash1 = (__int128)besthash1*powq1[j-bestJ]%MOD;
besthash2 = (__int128)besthash2*powq2[j-bestJ]%MOD;
} else {
currhash1 = (__int128)currhash1*powq1[bestJ-j]%MOD;
currhash2 = (__int128)currhash2*powq2[bestJ-j]%MOD;
}
// if (i == 1 && j == 2) {
// cout << "m " << m << '\n';
// cout << "besthashs " << besthash1 << " " << besthash2 << '\n';
// cout << "currhashs " << currhash1 << " " << currhash2 << '\n';
// }
if (besthash1 == currhash1 && besthash2 == currhash2) l = m+1;
else r = m-1;
}
if (l <= N/2*M/2) {
ll rowCnt = l/(M/2)+(l%(M/2)==0?-1:0);
ll remm = l%(M/2);
if (remm == 0) remm = M/2;
ll bestX = bestI+rowCnt, bestY = bestJ+remm-1;
bestX--;bestY--;
if (A[bestX][bestY] == 1) {
bestI = i;
bestJ = j;
}
}
}
}
for (int i = 0; i < N/2; i++) {
for (int j = 0; j < M/2; j++) {
if (A[bestI+i-1][bestJ+j-1] == 0) cout << '*';
else cout << '.';
}
cout << '\n';
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("paintbarn.in", "r", stdin);
// freopen("paintbarn.out", "w", stdout);
// ll caseCnt = 1;
// ll T;
// cin >> T;
// while (T--)
// {
solve();
// cout << "Case #"<< caseCnt << ": " << ans << '\n';
// caseCnt++;
// }
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1104 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1104 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1104 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
3 ms |
852 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
