제출 #1083715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083715		Thunnus	Sateliti (COCI20_satellti)	C++17	110 / 110	327 ms	102276 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int M = 1e9 + 9;
random_device rd;
const int B = uniform_int_distribution<>(31, 1000)(rd);

struct Hashing{
    vi phash, pw{1ll};

    Hashing(const vi &s) : phash(sz(s) + 1){
		pw.resize(sz(s) + 1);
        for(int i = 1; i <= sz(s); i++){
            pw[i] = (pw[i - 1] * B) % M;
            phash[i] = (phash[i - 1] * B + s[i - 1]) % M;
        }
    }

    inline int get_hash(int l, int r){
        int ret = phash[r + 1] - ((phash[l] * pw[r - l + 1]) % M);
        return (ret < 0 ? ret + M : ret);
    }
};

signed main(){
	//ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> word(2 * n);
    for(int i = 0; i < n; i++){
		cin >> word[i];
	}
    for(int i = n; i < 2 * n; i++){
        word[i - n] += word[i - n];
        word[i] = word[i - n];
    }

    vector<Hashing> hash, hash_hash;
    for(int i = 0; i < 2 * n; i++){
        hash.emplace_back(vi(word[i].begin(), word[i].end()));
    }
    for(int j = 0; j < m; j++){
        vi s;
        for(int i = 0; i < 2 * n; i++){
            s.emplace_back(hash[i].get_hash(j, j + m - 1));
        }
        hash_hash.emplace_back(s);
    }
	
    auto is_better = [&](const pii &a, const pii &b) -> bool {
        int lo = 0, hi = n, ret = 0, mid, h1, h2;
        while(hi >= lo){
            mid = lo + (hi - lo) / 2;
            h1 = hash_hash[a.se].get_hash(a.fi, a.fi + mid - 1), h2 = hash_hash[b.se].get_hash(b.fi, b.fi + mid - 1);
            if(h1 == h2){
                lo = mid + 1;
                ret = mid;
            }
            else{
                hi = mid - 1;
            }
        }
        if(ret == n) return false;

        int frst = ret;
        lo = 0, hi = m, ret = 0;
        while(hi >= lo){
            mid = lo + (hi - lo) / 2;
            h1 = hash[a.fi + frst].get_hash(a.se, a.se + mid - 1), h2 = hash[b.fi + frst].get_hash(b.se, b.se + mid - 1);
            if(h1 == h2){
                lo = mid + 1;
                ret = mid;
            }
            else{
                hi = mid - 1;
            }
        }
        assert(ret < m);
        
        return (word[a.fi + frst][a.se + ret] > word[b.fi + frst][b.se + ret]);
    };

    pii best = {0, 0};
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(is_better(best, {i, j})){
                best = {i, j};
            }
        }
    }

    for(int i = best.fi; i < best.fi + n; i++){
        for(int j = best.se; j < best.se + m; j++){
            cout << word[i][j];
        }
        cout << "\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60