| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1232848 | nhq0914 | Sateliti (COCI20_satellti) | C++17 | 0 ms | 0 KiB |
//a person woke up at the bottom of the abyss...
#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
using namespace std;
#ifdef my_local
const int mod = 1e9 + 7;
#else
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rd_mod(int l, int r){
function <bool(int)> is_prime = [&] {
if(n == 2 || n == 3) return true;
if(n < 3 || n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;
return true;
};
int num_mod = l + mt() % (r - l + 1);
while(not is_prime(num_mod)) ++num_mod;
return num_mod;
}
const int mod = rd_mod();
#endif
template <int _mod>
struct modint {
constexpr static int mod = _mod;
int m;
modint(int n = 0) : m(n) {}
modint(int64_t n) : m(n % mod) {}
inline modint operator += (const modint &x) {
m += x.m;
if(m >= mod) m -= mod;
return *this;
}
inline modint operator -= (const modint &x) {
m -= x.m;
if(m < 0) m += mod;
return *this;
}
inline modint operator *= (const modint &x) {
m = 1ll * m * x.m % mod;
return *this;
}
inline modint operator /= (const modint &x) {
return *this *= x.inv();
}
inline modint operator ^= (int p) {
modint res = 1;
while(p) {
if(p & 1) res *= *this;
*this *= *this;
p >>= 1;
}
return res;
}
modint inv() const {
modint t = *this;
return t ^= (mod - 2);
}
inline friend modint operator + (modint x, const modint &y) {return x += y;}
inline friend modint operator - (modint x, const modint &y) {return x -= y;}
inline friend modint operator * (modint x, const modint &y) {return x *= y;}
inline friend modint operator / (modint x, const modint &y) {return x /= y;}
inline friend modint operator ^ (modint x, const int &y) {return x ^= y;}
constexpr explicit operator bool () const {return m != 0;}
constexpr bool operator == (const modint &x) const {return m == x.m;}
constexpr bool operator != (const modint &x) const {return m != x.m;}
friend std::istream &operator >> (std::istream &in, modint &x) {int64_t n; in >> n; x = modint(n); return in;}
constexpr friend std::ostream &operator << (std::ostream &out, const modint &x) {out << x.m; return out;}
};
using mint = modint <mod>;
int n, m;
int ans_x, ans_y;
mint base_c = 29, base_r = 31;
mint pow_c[2001], pow_r[2001];
mint char_hash[2001][2001];
char a[2001][2001];
inline int w(char c) {
if(c == '.') return 9;
else return 11;
}
inline mint get_hash(int a, int b, int c, int d) {
return char_hash[c][d] -
char_hash[c][b - 1] * pow_c[d - b + 1] -
char_hash[a - 1][d] * pow_r[c - a + 1] +
char_hash[a - 1][b - 1] * pow_c[d - b + 1] * pow_r[c - a + 1];
}
int main(int argc, char const *argv[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
F(i, 1, n) F(j, 1, m) cin >> a[i][j];
F(i, n + 1, 2 * n) F(j, 1, m) a[i][j] = a[i - n][j];
F(i, 1, n) F(j, m + 1, 2 * m) a[i][j] = a[i][j - m];
F(i, n + 1, 2 * n) F(j, m + 1, 2 * m) a[i][j] = a[i - n][j - m];
// F(i, 1, 2 * n) {
// F(j, 1, 2 * m) cout << a[i][j];
// cout << '\n';
// }
pow_r[0] = 1, pow_c[0] = 1;;
F(i, 1, 2 * n) pow_r[i] = base_r * pow_r[i - 1];
F(i, 1, 2 * m) pow_c[i] = base_c * pow_c[i - 1];
F(i, 1, 2 * n) {
mint cur_hash = 0;
F(j, 1, 2 * m) {
cur_hash = base_c * cur_hash + w(a[i][j]);
char_hash[i][j] = base_r * char_hash[i - 1][j] + cur_hash;
}
}
ans_x = n;
ans_y = m;
F(i, n, 2 * n) F(j, m, 2 * m) {
static int l, r, mid, row, col;
l = i - n + 1, r = i, row = -1;
while(l <= r) {
mid = (l + r) / 2;
if(get_hash(ans_x - n + 1, ans_y - m + 1, ans_x - i + mid, ans_y) == get_hash(i - n + 1, j - m + 1, mid, j))
l = mid + 1;
else r = mid - 1, row = mid;
}
if(row == -1) continue;
l = j - m + 1, r = j, col = -1;
while(l <= r) {
mid = (l + r) / 2;
if(get_hash(ans_x - n + 1, ans_y - m + 1, ans_x - i + row, ans_y - j + mid) == get_hash(i - n + 1, j - m + 1, row, mid))
l = mid + 1;
else r = mid - 1, col = mid;
}
if(col == -1) continue;
if(a[row][col] < a[ans_x - i + row][ans_y - j + col])
ans_x = i, ans_y = j;
}
F(i, ans_x - n + 1, ans_x) {
F(j, ans_y - m + 1, ans_y) cout << a[i][j];
cout << '\n';
}
cerr << "runtime: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
}