#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> powq1(M+1);
powp1[0] = powq1[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;
}
function<ll(ll, ll)> addMod = [&](ll a, ll b) {
ll val = ((__int128)a+b)%MOD;
return val;
};
function<ll(ll, ll)> subMod = [&](ll a, ll b) {
ll val = ((__int128)a-b+MOD)%MOD;
return val;
};
// ll test = ((__int128)(1LL<<62)+(1LL<<62)+(1LL<<62)+(1LL<<62)+(1LL<<62))%MOD;
// cout << test << '\n';
// cout << MOD << '\n';
// cout << (1LL<<61) << '\n';
// cout << 1LL-(1LL<<62)-(1LL<<62) << '\n';
// cout << (subMod(1LL,(1LL<<55))) << '\n';
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]%MOD*powq1[j-1]%MOD;
// ll hash2 = (__int128)A[i-1][j-1]*powp2[i-1]%MOD*powq2[j-1]%MOD;
PSHASH1[i][j] = addMod(subMod(addMod(PSHASH1[i-1][j],PSHASH1[i][j-1]),PSHASH1[i-1][j-1]),hash1);
// PSHASH2[i][j] = addMod(subMod(addMod(PSHASH2[i-1][j],PSHASH2[i][j-1]),PSHASH2[i-1][j-1]),hash2);
PSHASH1ROW[i][j] = addMod(PSHASH1ROW[i][j-1],hash1);
// PSHASH2ROW[i][j] = addMod(PSHASH2ROW[i][j-1],hash2);
}
}
ll bestI = 1, bestJ = 1;
ll opCNt = 0;
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) {
opCNt++;
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 = subMod(addMod(subMod(subMod(PSHASH1[x1][y1],PSHASH1[x1][bestJ-1]),PSHASH1[bestI-1][y1]),PSHASH1[bestI-1][bestJ-1]),subMod(PSHASH1ROW[x1][y1],PSHASH1ROW[x1][bestJ+remm-1]));
// ll besthash2 = subMod(addMod(subMod(subMod(PSHASH2[x1][y1],PSHASH2[x1][bestJ-1]),PSHASH2[bestI-1][y1]),PSHASH2[bestI-1][bestJ-1]),subMod(PSHASH2ROW[x1][y1],PSHASH2ROW[x1][bestJ+remm-1]));
ll currhash1 = subMod(addMod(subMod(subMod(PSHASH1[x2][y2],PSHASH1[x2][j-1]),PSHASH1[i-1][y2]),PSHASH1[i-1][j-1]),subMod(PSHASH1ROW[x2][y2],PSHASH1ROW[x2][j+remm-1]));
// ll currhash2 = subMod(addMod(subMod(subMod(PSHASH2[x2][y2],PSHASH2[x2][j-1]),PSHASH2[i-1][y2]),PSHASH2[i-1][j-1]),subMod(PSHASH2ROW[x2][y2],PSHASH2ROW[x2][j+remm-1]));
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 == 35 && j == 15) {
// cout << "m " << m << '\n';
// cout << "besthashs " << besthash1 << " " << besthash2 << '\n';
// cout << "currhashs " << currhash1 << " " << currhash2 << '\n';
// }
if (besthash1 == currhash1) 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';
}
// cout << "OPCNT " << opCNt << '\n';
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("paintbarn2.in", "r", stdin);
// freopen("paintbarn2.out", "w", stdout);
// ll caseCnt = 1;
// ll T;
// cin >> T;
// while (T--)
// {
solve();
// cout << "Case #"<< caseCnt << ": " << ans << '\n';
// caseCnt++;
// }
return 0;
}
Compilation message
Main.cpp: In function 'll solve()':
Main.cpp:216:20: warning: unused variable 'p2' [-Wunused-variable]
216 | ll p1 = 2, p2 = 5, q1 = 3, q2 = 7;
| ^~
Main.cpp:216:36: warning: unused variable 'q2' [-Wunused-variable]
216 | ll p1 = 2, p2 = 5, q1 = 3, q2 = 7;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
592 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
592 KB |
Output is correct |
| 5 |
Correct |
3 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
592 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
592 KB |
Output is correct |
| 5 |
Correct |
3 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
720 KB |
Output is correct |
| 8 |
Correct |
125 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
4 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
129 ms |
10576 KB |
Output is correct |
| 12 |
Correct |
129 ms |
10816 KB |
Output is correct |
| 13 |
Correct |
115 ms |
11008 KB |
Output is correct |
| 14 |
Correct |
132 ms |
11004 KB |
Output is correct |
| 15 |
Correct |
114 ms |
11080 KB |
Output is correct |
| 16 |
Correct |
127 ms |
10996 KB |
Output is correct |
| 17 |
Correct |
158 ms |
11080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
592 KB |
Output is correct |
| 2 |
Correct |
3 ms |
760 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
592 KB |
Output is correct |
| 5 |
Correct |
3 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
720 KB |
Output is correct |
| 8 |
Correct |
125 ms |
10576 KB |
Output is correct |
| 9 |
Correct |
4 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
129 ms |
10576 KB |
Output is correct |
| 12 |
Correct |
129 ms |
10816 KB |
Output is correct |
| 13 |
Correct |
115 ms |
11008 KB |
Output is correct |
| 14 |
Correct |
132 ms |
11004 KB |
Output is correct |
| 15 |
Correct |
114 ms |
11080 KB |
Output is correct |
| 16 |
Correct |
127 ms |
10996 KB |
Output is correct |
| 17 |
Correct |
158 ms |
11080 KB |
Output is correct |
| 18 |
Correct |
1858 ms |
96016 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1616 KB |
Output is correct |
| 20 |
Correct |
22 ms |
2128 KB |
Output is correct |
| 21 |
Correct |
1695 ms |
96264 KB |
Output is correct |
| 22 |
Correct |
1773 ms |
96256 KB |
Output is correct |
| 23 |
Correct |
1579 ms |
96304 KB |
Output is correct |
| 24 |
Correct |
1851 ms |
96256 KB |
Output is correct |
| 25 |
Correct |
1640 ms |
96260 KB |
Output is correct |
| 26 |
Correct |
1957 ms |
96256 KB |
Output is correct |
| 27 |
Correct |
1958 ms |
96096 KB |
Output is correct |
