#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define _ << " , " <<
#define bug(x) cout << #x << " >>>>>>> " << x << endl;
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 2000000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9; //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Info {
int i, j, k, c;
string r;
Info(int _i, int _j, int _k, int _c, string _r) {
i = _i; j = _j; k = _k; c = _c; r = _r;
}
Info(){}
};
string image[2005];
string s;
vector<int> sa, c;
// O(n)
void countSort()
{
int n = sa.size();
vector<int> buc(n), new_sa(n);
for(int &w : sa)
buc[c[w]]++;
for(int i = 1; i < n; i++)
buc[i] += buc[i - 1];
for(int i = n - 1; i >= 0; i--)
new_sa[ --buc[ c[sa[i]] ] ] = sa[i];
sa = new_sa;
}
// O(|s| * log|s|)
void buildSuffixArray()
{
int n = s.size();
sa.resize(n);
c.resize(n);
for(int i = 0; i < n; i++)
sa[i] = i, c[i] = s[i];
sort(sa.begin(), sa.end(), [&](int a, int b)
{
return c[a] < c[b];
});
c[sa[0]] = 0;
for(int i = 1; i < n; i++)
if(s[sa[i - 1]] == s[sa[i]])
c[sa[i]] = c[sa[i - 1]];
else
c[sa[i]] = c[sa[i - 1]] + 1;
int k = 0;
while((1 << k) < n)
{
for(int i = 0; i < n; i++)
sa[i] = (sa[i] - (1 << k) + n) % n;
countSort();
vector<int> new_c(n);
new_c[sa[0]] = 0;
for(int i = 1; i < n; i++)
{
pair<int, int> prev = {c[sa[i - 1]], c[(sa[i - 1] + (1 << k)) % n]};
pair<int, int> cur = {c[sa[i]], c[(sa[i] + (1 << k)) % n]};
if(prev == cur) new_c[sa[i]] = new_c[sa[i - 1]];
else new_c[sa[i]] = new_c[sa[i - 1]] + 1;
}
c = new_c;
k++;
}
}
pair<string, int> smallest_cyclic_shift(string a) {
s = a;
sa.clear();
c.clear();
buildSuffixArray();
string ans;
for(int i = sa[0]; i < SZ(s); i++)
ans.push_back(s[i]);
for(int i = 0; i < sa[0]; i++)
ans.push_back(s[i]);
return {ans, sa[0]};
}
void solve(){
int n, m;
cin >> n >> m;
vector<int> mark(2 * n);
for(int i = 0; i < n; i++) {
cin >> image[i];
int v = count(image[i].begin(), image[i].end(), '.');
if(v == 0) mark[i] = 1;
else if(v == m) mark[i] = -1;
}
for(int i = 0; i < n; i++)
image[i + n] = image[i], mark[i + n] = mark[i];
vector<Info> aux;
for(int i = 0; i < n; i++) {
if(mark[i] == -1) continue;
int d = -1, k = -1, last = -1; // pos with dots
for(int j = i; j < i + n; j++) {
if(d == -1 and mark[j] == -1) d = j;
if(k == -1 and mark[j] == 0) k = j;
if(mark[j] == 1) last = j;
}
if(d == -1 or d > k) d = k;
if(d == -1 or k == -1) d = k = last;
if(k == -1) continue;
auto [a, c] = smallest_cyclic_shift(image[ k ]);
aux.push_back(Info(i, d, k, c, a));
}
sort(aux.begin(), aux.end(),
[](Info a, Info b) {
if(a.j - a.i != b.j - b.i)
return a.j - a.i > b.j - b.i;
return a.r < b.r;
}
);
if(aux.empty()) {
for(int i = 0; i < n; i++)
cout << image[i] << '\n';
return;
}
// for(int i = 0; i < SZ(aux); i++)
// bug(aux[i].i _ aux[i].j _ aux[i].k _ aux[i].c _ aux[i].r);
for(int i = 0; i < 2 * n; i++)
image[i] += image[i];
for(int i = aux[0].i; i < aux[0].i + n; i++) {
for(int j = aux[0].c; j < aux[0].c + m; j++)
cout << image[i][j];
cout << '\n';
}
}
int32_t main() {
fastio;
int t = 1;
//cin >> t;
for(int caso = 1; caso <= t; ++caso) {
//cout << "Case #" << caso << ": ";
solve();
}
return 0;
}
/*
Before submit:
Check the corners cases
Check solution restrictions
For implementation solutions:
Check the flow of the variables
For intervals problems:
Think about two pointers
For complete search:
Think about cuts
If you get WA:
Reread your code looking for stupid typos
Try various manual testcases
Recheck the correctness of your algorithm
Reread the statement
Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
Change the coder (if you're with a team)
Give up. You may have other tasks to solve.
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
