oj.uz

Submission #704802

# Submission time Handle Problem Language Result Execution time Memory
704802 2023-03-03T03:56:48 Z PixelCat Sateliti (COCI20_satellti) C++14
110 / 110
 356 ms 88944 KB 
/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
using LLL = __int128_t;
using pii = pair<int, int>;
 
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#endif

const int MAXN = 2010;

const int B1 = 5;
const int B2 = 7;
const int M1 = 998244353;
const int M2 = 1000000007;
int p1[MAXN];
int p2[MAXN];

int g[MAXN][MAXN];
int hr[MAXN][MAXN];
int hc[MAXN][MAXN];
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    p1[0] = p2[0] = 1;
    For(i, 1, MAXN - 1) {
        p1[i] = p1[i - 1] * B1 % M1;
        p2[i] = p2[i - 1] * B2 % M2;
    }
    int n, m; cin >> n >> m;
    For(i, 1, n) For(j, 1, m) {
        char ch; cin >> ch;
        int x = (ch == '.');
        g[i][j] = g[i + n][j] = g[i][j + m] = g[i + n][j + m] = x;
    }
    For(i, 1, n * 2) {
        For(j, 1, m * 2) {
            hr[i][j] = (hr[i][j - 1] * B1 + g[i][j]) % M1;
        }
    }
    For(j, 1, m) {
        For(i, 1, n * 2) {
            int h = (hr[i][j + m - 1] - hr[i][j - 1] * p1[m]) % M1;
            h += M1 * (h < 0);
            hc[i][j] = (hc[i - 1][j] * B2 + h) % M2;
        }
    }
    auto getc = [&](int i, int j, int len) {
        int res = (hc[i + len - 1][j] - hc[i - 1][j] * p2[len]) % M2;
        return (res + M2 * (res < 0));
    };
    auto getr = [&](int i, int j, int len) {
        int res = (hr[i][j + len - 1] - hr[i][j - 1] * p1[len]) % M1;
        return (res + M1 * (res < 0));
    };
    auto smol = [&](int i1, int j1, int i2, int j2) {
        int lo = 0, hi = n + 1;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            int h1 = getc(i1, j1, mi);
            int h2 = getc(i2, j2, mi);
            if(h1 == h2) lo = mi;
            else hi = mi;
        }
        if(lo == n) return false;
        int r = lo;
        lo = 0; hi = m + 1;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            int h1 = getr(i1 + r, j1, mi);
            int h2 = getr(i2 + r, j2, mi);
            if(h1 == h2) lo = mi;
            else hi = mi;
        }
        assert(lo < m);
        // cerr << i1 << " " << j1 << " " << i2 << " " << j2 << " " << r << " " << lo << "\n";
        return g[i1 + r][j1 + lo] < g[i2 + r][j2 + lo];
    };
    int i0 = 1, j0 = 1;
    For(i, 1, n) For(j, 1, m) {
        if(!smol(i0, j0, i, j)) {
            i0 = i; j0 = j;
        }
    }
    For(i, 0, n - 1) {
        For(j, 0, m - 1) cout << "*."[g[i + i0][j + j0]];
        cout << "\n";
    }
    // For(i, 1, n * 2) {
    //     For(j, 1, m * 2) cout << "*."[g[i][j]];
    //     cout << "\n";
    // }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 1 ms 1640 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 2 ms 1776 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 1 ms 1640 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 2 ms 1776 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 29 ms 14252 KB Output is correct
9 Correct 1 ms 744 KB Output is correct
10 Correct 4 ms 7528 KB Output is correct
11 Correct 26 ms 14272 KB Output is correct
12 Correct 27 ms 14572 KB Output is correct
13 Correct 26 ms 14796 KB Output is correct
14 Correct 29 ms 14752 KB Output is correct
15 Correct 28 ms 14796 KB Output is correct
16 Correct 29 ms 14768 KB Output is correct
17 Correct 30 ms 14752 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 1 ms 1640 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 2 ms 1776 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 29 ms 14252 KB Output is correct
9 Correct 1 ms 744 KB Output is correct
10 Correct 4 ms 7528 KB Output is correct
11 Correct 26 ms 14272 KB Output is correct
12 Correct 27 ms 14572 KB Output is correct
13 Correct 26 ms 14796 KB Output is correct
14 Correct 29 ms 14752 KB Output is correct
15 Correct 28 ms 14796 KB Output is correct
16 Correct 29 ms 14768 KB Output is correct
17 Correct 30 ms 14752 KB Output is correct
18 Correct 322 ms 88784 KB Output is correct
19 Correct 14 ms 25300 KB Output is correct
20 Correct 5 ms 2040 KB Output is correct
21 Correct 284 ms 88944 KB Output is correct
22 Correct 346 ms 88848 KB Output is correct
23 Correct 307 ms 88848 KB Output is correct
24 Correct 356 ms 88932 KB Output is correct
25 Correct 297 ms 88856 KB Output is correct
26 Correct 332 ms 88916 KB Output is correct
27 Correct 347 ms 88732 KB Output is correct