/* nya */
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int long long
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
using LLL = __int128_t;
using pii = pair<int, int>;
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
const int MAXN = 1024;
pii i2p(int id) {
return pii(id >> 10, id & 1023);
}
int p2i(int a, int b) {
return (a << 10) | b;
}
int n, m;
char g[MAXN][MAXN];
int val[MAXN][MAXN];
int sa[MAXN * MAXN];
int rk[MAXN * MAXN];
int tmp[MAXN * MAXN];
void getSA(function<int(int, int)> nxt) {
int nm = n * m;
int *r = rk;
int *r2 = tmp;
For(i, 0, n - 1) For(j, 0, m - 1) {
sa[i * m + j] = p2i(i, j);
r[p2i(i, j)] = val[i][j];
}
sort(sa, sa + nm, [&](int a, int b) {
return r[a] < r[b];
});
for(int len = 1; len < 1024; len <<= 1) {
auto cmp = [&](int a, int b) {
if(r[a] != r[b]) return r[a] < r[b];
a = nxt(a, len); b = nxt(b, len);
return r[a] < r[b];
};
sort(sa, sa + nm, cmp);
r2[sa[0]] = 0;
For(i, 1, nm - 1) r2[sa[i]] = r2[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
swap(r, r2);
}
if(r != rk) {
For(i, 0, nm - 1) rk[i] = tmp[i];
}
}
int nxt1(int id, int len) {
pii p = i2p(id);
return p2i(p.F, (p.S + len) % m);
}
int nxt2(int id, int len) {
pii p = i2p(id);
return p2i((p.F + len) % n, p.S);
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// OAO
cin >> n >> m;
For(i, 0, n - 1) For(j, 0, m - 1) {
char ch; cin >> ch;
val[i][j] = (ch == '.');
g[i][j] = ch;
}
getSA(nxt1);
For(i, 0, n - 1) For(j, 0, m - 1) {
auto id = p2i(i, j);
val[i][j] = rk[id];
}
getSA(nxt1);
auto p = i2p(sa[0]);
int x = p.F, y = p.S;
For(i, 0, n - 1) {
For(j, 0, m - 1) cout << g[(x + i) % n][(y + j) % m];
cout << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Correct |
3 ms |
840 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Correct |
3 ms |
840 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Correct |
3 ms |
840 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
