제출 #1293645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293645		mwen	Sateliti (COCI20_satellti)	C++20	110 / 110	367 ms	33772 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

constexpr ll MOD = 1e9+7;
constexpr ll x = 31;
constexpr ll y = 37;

int id(char c) {
    if(c == '*')
        return 1;
    return 2;
}

int main() {
    vector<ll> xPow(3000), yPow(3000);
    xPow[0] = yPow[0] = 1;
    for(int i = 1; i < 3000; i++) {
        xPow[i] = xPow[i-1]*x%MOD;
        yPow[i] = yPow[i-1]*y%MOD;
    }
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for(int i = 0; i < n; i++)
        cin >> grid[i];
        
    auto get = [&](int r, int c) {
        return grid[r%n][c%m];
    };
    
    vector<vector<ll>> p(2*n+1, vector<ll>(2*m+1));
    for(int r = 0; r < 2*n; r++) {
        for(int c = 0; c < 2*m; c++) {
            int ch = id(get(r,c));
            p[r+1][c+1] =(p[r][c+1]*y%MOD 
                        + p[r+1][c]*x%MOD 
                        - p[r][c]*x%MOD*y%MOD
                        + ch
                        + MOD)%MOD;
        }
    }
    auto rect = [&](int r1, int c1, int r2, int c2) {
        int dy = r2-r1+1;
        int dx = c2-c1+1;
        return  (p[r2+1][c2+1]
               - p[r1][c2+1]*yPow[dy]%MOD
               - p[r2+1][c1]*xPow[dx]%MOD
               + p[r1][c1]*yPow[dy]%MOD*xPow[dx]%MOD
               + MOD + MOD)%MOD;
    };
    
    //is a < b
    auto comp = [&](int r1, int c1, int r2, int c2) {
        int l = 0, r = n-1;
        int h = 0;
        while(l <= r) {
            int mid = (l+r)/2;
            if(rect(r1, c1, r1+mid-1, c1+m-1) == rect(r2, c2, r2+mid-1, c2+m-1)) {
                h = mid;
                l = mid+1;
            }
            else
                r = mid-1;
        }
        int w = 0;
        l = 0, r = m-1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(rect(r1+h, c1, r1+h, c1+mid-1) == rect(r2+h, c2, r2+h, c2+mid-1)) {
                w = mid;
                l = mid+1;
            }
            else
                r = mid-1;
        }
        return id(get(r1+h, c1+w)) < id(get(r2+h, c2+w));
    };
    
    int bestR = 0, bestC = 0;
    for(int r = 0; r < n; r++) {
        for(int c = 0; c < m; c++) {
            if(comp(r, c, bestR, bestC)) {
                bestR = r;
                bestC = c;
            }
        }
    }
    for(int r = 0; r < n; r++) {
        for(int c = 0; c < m; c++) {
            cout << grid[(r+bestR)%n][(c+bestC)%m];
        }
        cout << "\n";
    }
}

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