oj.uz

Submission #755290

# Submission time Handle Problem Language Result Execution time Memory
755290 2023-06-09T17:24:09 Z KKT89 Sateliti (COCI20_satellti) C++17
110 / 110
 277 ms 37712 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

// https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_C
template <ull b1 = 9973, ull b2 = 1000000007>
struct rolling_hash2 {
    const int h, w;
    vector<ull> rh, rw;
    vector<vector<ull>> hs;
    template <class T> rolling_hash2(const vector<vector<T>>& a)
        : h(a.size()), w(a[0].size()), rh(h+1), rw(w+1), hs(h+1, vector<ull>(w+1))
    {
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                hs[i+1][j+1] = hs[i+1][j] * b2 + a[i][j];
            }
            for (int j = 0; j < w; ++j) {
                hs[i+1][j+1] += hs[i][j+1] * b1;
            }
        }
        rh[0] = rw[0] = 1;
        for (int i = 0; i < h; ++i) {
            rh[i+1] = rh[i] * b1;
        }
        for (int i = 0; i < w; ++i) {
            rw[i+1] = rw[i] * b2;
        }
    }
    ull get(int i1, int j1, int i2, int j2) {
        assert(0 <= i1 and i1 <= i2 and i2 <= h);
        assert(0 <= j1 and j1 <= j2 and j2 <= w);
        ull u = hs[i2][j2] - hs[i2][j1] * rw[j2 - j1];
        ull d = hs[i1][j2] - hs[i1][j1] * rw[j2 - j1];
        return u - d * rh[i2 - i1];
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h,w; cin >> h >> w;
    vector<vector<char>> a(h*2, vector<char>(w*2));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> a[i][j];
            a[i][j+w] = a[i][j];
            a[i+h][j] = a[i][j];
            a[i+h][j+w] = a[i][j];
        }
    }

    rolling_hash2 rha(a);

    int ans_i = 0, ans_j = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            int lh = 0, rh = h+1;
            while (rh - lh > 1) {
                int mh = (lh + rh) / 2;
                if (rha.get(ans_i, ans_j, ans_i+mh, ans_j+w) == rha.get(i, j, i+mh, j+w)) {
                    lh = mh;
                }
                else {
                    rh = mh;
                }
            }
            if (lh == h) continue;
            int l = 0, r = w+1;
            while (r - l > 1) {
                int m = (l+r)/2;
                if (rha.get(ans_i+lh, ans_j, ans_i+lh+1, ans_j+m) == rha.get(i+lh, j, i+lh+1, j+m)) {
                    l = m;
                }
                else {
                    r = m;
                }
            }
            if (l != w) {
                if (a[i+lh][j+l] < a[ans_i+lh][ans_j+l]) {
                    ans_i = i;
                    ans_j = j;
                }
            }
        }
    }

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cout << a[i+ans_i][j+ans_j];
        }
        cout << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 20 ms 3532 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 20 ms 3528 KB Output is correct
12 Correct 20 ms 3528 KB Output is correct
13 Correct 20 ms 3664 KB Output is correct
14 Correct 21 ms 3732 KB Output is correct
15 Correct 20 ms 3636 KB Output is correct
16 Correct 21 ms 3640 KB Output is correct
17 Correct 22 ms 3768 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 20 ms 3532 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 20 ms 3528 KB Output is correct
12 Correct 20 ms 3528 KB Output is correct
13 Correct 20 ms 3664 KB Output is correct
14 Correct 21 ms 3732 KB Output is correct
15 Correct 20 ms 3636 KB Output is correct
16 Correct 21 ms 3640 KB Output is correct
17 Correct 22 ms 3768 KB Output is correct
18 Correct 257 ms 37540 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 5 ms 980 KB Output is correct
21 Correct 235 ms 37712 KB Output is correct
22 Correct 265 ms 37712 KB Output is correct
23 Correct 232 ms 37704 KB Output is correct
24 Correct 256 ms 37704 KB Output is correct
25 Correct 234 ms 37708 KB Output is correct
26 Correct 277 ms 37696 KB Output is correct
27 Correct 258 ms 37576 KB Output is correct