#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, m;
namespace sub1{
void solve(){
vector<string>a(n);
for(string& s : a){
cin >> s;
}
vector<string>ans = a;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
vector<string>b;
for(int k = i; k < n; k++){
b.emplace_back(a[k].substr(j, m - j) + a[k].substr(0, j));
}
for(int k = 0; k < i; k++){
b.emplace_back(a[k].substr(j, m - j) + a[k].substr(0, j));
}
minimize(ans, b);
}
}
for(string& s : ans){
cout << s << "\n";
}
}
}
namespace sub23{
const int lim = 2e3 + 5;
const int mod = 1e9 + 9;
void add(int& a, int b){
if((a += b) >= mod){
a -= mod;
}
}
int power(int a, int b){
int ans = 1;
for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
if(b & 1){
ans = 1LL * ans * a % mod;
}
}
return ans;
}
int pw_row[lim], pw_col[lim], inv_row[lim], inv_col[lim], hash_v[lim][lim];
bitset<lim>a[lim];
int get_hash(int x, int y, int u, int v){
return 1LL * (((hash_v[u][v] - hash_v[x - 1][v] - hash_v[u][y - 1] + hash_v[x - 1][y - 1]) % mod + mod) % mod) * inv_row[x - 1] % mod * inv_col[y - 1] % mod;
}
void solve(){
for(int i = 0; i < lim; i++){
a[i].reset();
}
for(int i = pw_row[0] = pw_col[0] = inv_row[0] = inv_col[0] = 1; i < lim; i++){
pw_row[i] = (pw_row[i - 1] << 1) % mod;
pw_col[i] = 3LL * pw_col[i - 1] % mod;
}
inv_row[lim - 1] = power(pw_row[lim - 1], mod - 2);
inv_col[lim - 1] = power(pw_col[lim - 1], mod - 2);
for(int i = lim - 2; i > 0; i--){
inv_row[i] = (inv_row[i + 1] << 1) % mod;
inv_col[i] = 3LL * inv_col[i + 1] % mod;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char c;
cin >> c;
if(c == '.'){
a[i].set(j);
a[i].set(j + m);
a[i + n].set(j);
a[i + n].set(j + m);
}
}
}
memset(hash_v, 0, sizeof(hash_v));
for(int i = 1; i <= (n << 1); i++){
for(int j = 1, sum = 0; j <= (m << 1); j++){
if(a[i].test(j)){
add(sum, 1LL * pw_row[i] * pw_col[j] % mod);
}
hash_v[i][j] = (hash_v[i - 1][j] + sum) % mod;
}
}
int x = 1, y = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int low = 0, high = n - 1, p = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(get_hash(i, j, i + mid, j + m - 1) == get_hash(x, y, x + mid, y + m - 1)){
low = p = mid + 1;
}
else{
high = mid - 1;
}
}
if(p < n){
int pp = high = m - 1;
low = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(get_hash(i + p, j, i + p, j + mid) != get_hash(x + p, y, x + p, y + mid)){
high = (pp = mid) - 1;
}
else{
low = mid + 1;
}
}
if(!a[i + p].test(j + pp)){
x = i;
y = j;
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << (a[i + x].test(j + y) ? '.' : '*');
}
cout << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> m;
if(max(n, m) <= 50){
sub23::solve();
}
else{
sub23::solve();
}
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:134:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |