| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 514070 |
2022-01-18T03:05:22 Z |
KoD |
Sateliti (COCI20_satellti) |
C++17 |
|
3 ms |
332 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using u64 = std::uint64_t;
using u128 = std::uint64_t;
constexpr u64 MOD = ((u64)1 << 61) - 1;
struct Fp {
u64 x;
Fp(const u64 x = 0) : x(x) {}
Fp& operator+=(const Fp& t) {
if ((x += t.x) >= MOD) x -= MOD;
return *this;
}
Fp& operator-=(const Fp& t) {
if (x < t.x) x += MOD;
x -= t.x;
return *this;
}
Fp& operator*=(const Fp& t) {
const auto y = (u128)x * t.x;
x = (y >> 61) + (y & MOD);
if (x >= MOD) x -= MOD;
return *this;
}
Fp operator+(const Fp& t) const {
return Fp(*this) += t;
}
Fp operator-(const Fp& t) const {
return Fp(*this) -= t;
}
Fp operator*(const Fp& t) const {
return Fp(*this) *= t;
}
bool operator==(const Fp& t) const {
return x == t.x;
}
};
constexpr u64 Bx = 123456789;
constexpr u64 By = 987654321;
template <u64 B> Fp pow(const int n) {
static vector<Fp> vec = {1};
while ((int)vec.size() <= n) {
vec.push_back(vec.back() * B);
}
return vec[n];
}
template <class F> int binary_search(int ok, int ng, const F& f) {
while (std::abs(ok - ng) > 1) {
const int md = (ok + ng) / 2;
(f(md) ? ok : ng) = md;
}
return ok;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
vector grid(2 * N, vector<char>(2 * M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
char c;
std::cin >> c;
grid[i][j] = grid[i + N][j] = grid[i][j + M] = grid[i + N][j + M] = c;
}
}
vector hash(2 * N + 1, vector<Fp>(2 * M + 1));
for (int i = 0; i < 2 * N; ++i) {
for (int j = 0; j < 2 * M; ++j) {
hash[i + 1][j + 1] += grid[i][j];
hash[i + 1][j + 1] += hash[i][j + 1] * Bx;
hash[i + 1][j + 1] += hash[i + 1][j] * By;
hash[i + 1][j + 1] -= hash[i][j] * Bx * By;
}
}
const auto rect = [&](const int i, const int j, const int k, const int l) {
Fp ret = 0;
ret += hash[k][l];
ret -= hash[i][l] * pow<Bx>(k - i);
ret -= hash[k][j] * pow<By>(l - j);
ret += hash[i][j] * pow<Bx>(k - i) * pow<By>(l - j);
return ret;
};
int x = 0, y = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (rect(x, y, x + N, y + M) == rect(i, j, i + N, j + M)) {
continue;
}
const int h = binary_search(0, N, [&](const int thres) {
return rect(x, y, x + thres, y + M) == rect(i, j, i + thres, j + M);
});
const int w = binary_search(0, M, [&](const int thres) {
return rect(x + h, y, x + h + 1, y + thres) == rect(i + h, j, i + h + 1, j + thres);
});
if (grid[x + h][y + w] > grid[i + h][j + w]) {
x = i, y = j;
}
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
std::cout << grid[x + i][y + j];
}
std::cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
