제출 #755290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755290		KKT89	Sateliti (COCI20_satellti)	C++17	110 / 110	277 ms	37712 KiB

Main

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