Submission #704802

#	Time	Username	Problem	Language	Result	Execution time	Memory
704802		PixelCat	Sateliti (COCI20_satellti)	C++14	110 / 110	356 ms	88944 KiB

Main

/* 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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60