#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
const int N = 1e3 + 5;
const int NN = 2e3 + 5;
const int K = 4e6 + 5;
struct vec {
int f[NN];
int& operator[] (const int a) {return f[a];}
};
struct mat {
vec f[NN];
vec& operator[] (const int a) {return f[a];}
void operator= (const mat &g) {
for(int i = 0; i < NN; ++i)
memcpy(f[i].f, g.f[i].f, NN << 2);
}
};
int n, m, nn, mm, d;
mat a, A, z;
int fst[K], lst[K], nxt[K], vl[K], t, e[K], ne;
list<int> s[K];
inline void add(const int &i, const int &j) {
umax(d, i + 1);
s[i].push_back(j);
}
inline void iterate(const int &i) {
for(int j : s[i]) e[ne++] = j;
s[i].clear();
}
typedef pair<pii, pii> ppp;
ppp f[K]; int nf;
void combine(mat &a, mat &b, mat &c, int dx, int dy) {
nf = 0;
for(int i = 0; i + dx < nn; ++i)
for(int j = 0; j + dy < mm; ++j)
f[nf++] = {{a[i][j], b[i + dx][j + dy]}, {i, j}};
d = t = 0;
for(int i = 0; i < nf; ++i)
add(f[i].ft.sd, i);
ne = 0;
for(int i = 0; i < d; ++i)
iterate(i);
d = t = 0;
for(int i = 0; i < ne; ++i)
add(f[e[i]].ft.ft, e[i]);
ne = 0;
for(int i = 0; i < d; ++i)
iterate(i);
int s = 0;
for(int i = 0; i < nf; ++i) {
auto &g = f[e[i]];
if(i && g.ft != f[e[i - 1]].ft)
++s;
c[g.sd.ft][g.sd.sd] = s;
}
for(int i = nn - dx; i < nn; ++i)
for(int j = mm - dy; j < mm; ++j)
c[i][j] = s + 1;
}
void solve() {
memset(fst, -1, sizeof fst);
cin >> n >> m;
for(int i = 0; i < n + n; ++i) {
for(int j = 0; j < m + m; ++j) {
if(i < n && j < m) {
char c; cin >> c;
a[i][j] = c == '.';
} else
a[i][j] = a[i % n][j % m];
}
}
z = a;
nn = n << 1;
mm = m << 1;
bool empty = true;
for(int i = 0, u = m; ; ++i) {
if(i) combine(a, a, a, 0, 1 << i - 1);
if(u & 1 << i) {
if(empty) {
A = a;
empty = false;
} else
combine(a, A, A, 0, 1 << i);
u ^= 1 << i;
if(!u) break;
}
}
a = A;
empty = true;
for(int i = 0, u = n; ; ++i) {
if(i) combine(a, a, a, 1 << i - 1, 0);
if(u & 1 << i) {
if(empty) {
A = a;
empty = false;
} else
combine(a, A, A, 1 << i, 0);
u ^= 1 << i;
if(!u) break;
}
}
int x = 0, y = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(A[i][j] < A[x][y])
x = i, y = j;
for(int i = 0; i < n; ++i, cout << '\n')
for(int j = 0; j < m; ++j) cout << (z[x + i][y + j] ? '.' : '*');
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:117:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
117 | if(i) combine(a, a, a, 0, 1 << i - 1);
| ~~^~~
Main.cpp:131:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
131 | if(i) combine(a, a, a, 1 << i - 1, 0);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
157676 KB |
Output is correct |
| 2 |
Correct |
120 ms |
157548 KB |
Output is correct |
| 3 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 4 |
Correct |
115 ms |
157676 KB |
Output is correct |
| 5 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 6 |
Correct |
122 ms |
157548 KB |
Output is correct |
| 7 |
Correct |
127 ms |
157664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
157676 KB |
Output is correct |
| 2 |
Correct |
120 ms |
157548 KB |
Output is correct |
| 3 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 4 |
Correct |
115 ms |
157676 KB |
Output is correct |
| 5 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 6 |
Correct |
122 ms |
157548 KB |
Output is correct |
| 7 |
Correct |
127 ms |
157664 KB |
Output is correct |
| 8 |
Execution timed out |
3088 ms |
174780 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
157676 KB |
Output is correct |
| 2 |
Correct |
120 ms |
157548 KB |
Output is correct |
| 3 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 4 |
Correct |
115 ms |
157676 KB |
Output is correct |
| 5 |
Correct |
123 ms |
157548 KB |
Output is correct |
| 6 |
Correct |
122 ms |
157548 KB |
Output is correct |
| 7 |
Correct |
127 ms |
157664 KB |
Output is correct |
| 8 |
Execution timed out |
3088 ms |
174780 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
