oj.uz

Submission #704807

# Submission time Handle Problem Language Result Execution time Memory
704807 2023-03-03T04:02:12 Z PixelCat Sateliti (COCI20_satellti) C++14
110 / 110
 361 ms 88068 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 = 7;
const int B2 = 7;
const int M1 = 998244353;
// const int M2 = 1000000007;
const int M2 = M1;
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 1 ms 1748 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 2 ms 1620 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 1728 KB Output is correct
7 Correct 2 ms 1760 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 2 ms 1620 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 1728 KB Output is correct
7 Correct 2 ms 1760 KB Output is correct
8 Correct 28 ms 14308 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct
11 Correct 36 ms 14284 KB Output is correct
12 Correct 30 ms 14596 KB Output is correct
13 Correct 32 ms 14768 KB Output is correct
14 Correct 37 ms 14744 KB Output is correct
15 Correct 26 ms 14804 KB Output is correct
16 Correct 28 ms 14756 KB Output is correct
17 Correct 31 ms 14756 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 2 ms 1620 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 1728 KB Output is correct
7 Correct 2 ms 1760 KB Output is correct
8 Correct 28 ms 14308 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct
11 Correct 36 ms 14284 KB Output is correct
12 Correct 30 ms 14596 KB Output is correct
13 Correct 32 ms 14768 KB Output is correct
14 Correct 37 ms 14744 KB Output is correct
15 Correct 26 ms 14804 KB Output is correct
16 Correct 28 ms 14756 KB Output is correct
17 Correct 31 ms 14756 KB Output is correct
18 Correct 310 ms 87884 KB Output is correct
19 Correct 14 ms 25300 KB Output is correct
20 Correct 7 ms 2004 KB Output is correct
21 Correct 298 ms 87868 KB Output is correct
22 Correct 361 ms 87868 KB Output is correct
23 Correct 304 ms 88068 KB Output is correct
24 Correct 342 ms 88052 KB Output is correct
25 Correct 293 ms 88028 KB Output is correct
26 Correct 351 ms 88012 KB Output is correct
27 Correct 348 ms 87888 KB Output is correct