oj.uz

답안 #704805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704805 2023-03-03T04:01:40 Z PixelCat Sateliti (COCI20_satellti) C++14
110 / 110
 343 ms 88408 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;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 28 ms 14192 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 3 ms 7508 KB Output is correct
11 Correct 27 ms 14192 KB Output is correct
12 Correct 28 ms 14420 KB Output is correct
13 Correct 28 ms 14708 KB Output is correct
14 Correct 29 ms 14656 KB Output is correct
15 Correct 26 ms 14688 KB Output is correct
16 Correct 27 ms 14668 KB Output is correct
17 Correct 28 ms 14676 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 28 ms 14192 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 3 ms 7508 KB Output is correct
11 Correct 27 ms 14192 KB Output is correct
12 Correct 28 ms 14420 KB Output is correct
13 Correct 28 ms 14708 KB Output is correct
14 Correct 29 ms 14656 KB Output is correct
15 Correct 26 ms 14688 KB Output is correct
16 Correct 27 ms 14668 KB Output is correct
17 Correct 28 ms 14676 KB Output is correct
18 Correct 343 ms 88068 KB Output is correct
19 Correct 20 ms 25300 KB Output is correct
20 Correct 5 ms 2004 KB Output is correct
21 Correct 292 ms 88312 KB Output is correct
22 Correct 343 ms 88312 KB Output is correct
23 Correct 297 ms 88300 KB Output is correct
24 Correct 338 ms 88396 KB Output is correct
25 Correct 292 ms 88296 KB Output is correct
26 Correct 341 ms 88408 KB Output is correct
27 Correct 339 ms 88176 KB Output is correct