#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 2e3 + 100;
const int MOD = 1e9 + 7;
int N, M, arr[MX][MX];
int pref[MX][MX], h[MX][MX], x[MX][MX];
int add(int a, int b){
a += b;
if(a < 0) a += MOD;
if(a >= MOD) a -= MOD;
return a;
}
int que(int a, int b, int c, int d){
int ans = pref[c][d];
if(a > 0) ans = add(ans, -pref[a - 1][d]);
if(b > 0) ans = add(ans, -pref[c][b - 1]);
if(a > 0 && b > 0) ans = add(ans, pref[a - 1][b - 1]);
return ans;
}
int inv(int a){
int r = 1, b = MOD - 2;
while(b){
if(b & 1) r = 1ll * r * a % MOD;
a = 1ll * a * a % MOD;
b >>= 1;
}
return r;
}
int off(int fi, int fj, int si, int sj, int di, int dj){
int _i = ((si + di) % N < (fi + di) % N) ? 0 : fi + di;
int _j = ((sj + dj) % N < (fj + dj) % N) ? 0 : fj + dj;
return 1ll * que(fi + di, fj + dj, si + di, sj + dj) * inv(x[_i][_j]) % MOD;
}
bool cmp(int ai, int aj, int bi, int bj){
int v = -1;
{
int l = 0, r = N - 1;
while(l <= r){
int mid = l + r >> 1;
if(off(0, 0, mid, M - 1, ai, aj) == off(0, 0, mid, M - 1, bi, bj)){
l = mid + 1; v = mid;
}else{
r = mid - 1;
}
}
v++;
}
int h = -1;
{
int l = 0, r = M - 1, memo = -1;
while(l <= r){
int mid = l + r >> 1;
if(off(0, 0, v, mid, ai, aj) == off(0, 0, v, mid, bi, bj)){
l = mid + 1; h = mid;
}else{
r = mid - 1;
}
}
h++;
}
if(arr[(v + ai) % N][(h + aj) % M] > arr[(v + bi) % N][(h + bj) % M]) return true;
else return false;
}
char tmp[MX][MX];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
char c; cin >> c; tmp[i][j] = c;
arr[i][j] = (c == '*');
}
}
int curr = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
x[i][j] = curr;
h[i][j] = arr[i][j] * curr;
{
pref[i][j] = h[i][j];
if(i > 0) pref[i][j] = add(pref[i][j], pref[i - 1][j]);
if(j > 0) pref[i][j] = add(pref[i][j], pref[i][j - 1]);
if(i > 0 && j > 0) pref[i][j] = add(pref[i][j], -pref[i - 1][j - 1]);
}
if(j == M - 1) curr = 1ll * curr * 3 % MOD;
else curr = 1ll * curr * 2 % MOD;
}
}
for(int i = 0; i < 2 * N; i++){
for(int j = 0; j < 2 * M; j++){
x[i][j] = x[i % N][j % M];
h[i][j] = h[i % N][j % M];
{
pref[i][j] = h[i][j];
if(i > 0) pref[i][j] = add(pref[i][j], pref[i - 1][j]);
if(j > 0) pref[i][j] = add(pref[i][j], pref[i][j - 1]);
if(i > 0 && j > 0) pref[i][j] = add(pref[i][j], -pref[i - 1][j - 1]);
}
}
}
int _i = 0, _j = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(cmp(i, j, _i, _j)) _i = i, _j = j;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << tmp[(i + _i) % N][(j + _j) % M];
}
cout << '\n';
}
}
Compilation message
Main.cpp: In function 'bool cmp(int, int, int, int)':
Main.cpp:53:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = l + r >> 1;
| ~~^~~
Main.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = l + r >> 1;
| ~~^~~
Main.cpp:66:25: warning: unused variable 'memo' [-Wunused-variable]
66 | int l = 0, r = M - 1, memo = -1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1740 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
1800 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1740 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
1800 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1740 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
1800 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
