Submission #1293410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293410		vk3601h	Sateliti (COCI20_satellti)	C++20	0 / 110	1 ms	568 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long rng(long long low, long long high){
    static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<long long>(low, high)(gen);
}

const long long M = (1ll << 61) - 1;
const long long B = rng((1ll << 20), (1ll << 40));

long long mod_mul(long long a, long long b) {return (__int128)a * b % M;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int row_num, col_num;
    cin >> row_num >> col_num;

    vector<vector<char>> grid(2 * row_num, vector<char>(2 * col_num));
    for (int r = 0; r < row_num; r++){
        for (int c = 0; c < col_num; c++){
            char ch;
            cin >> ch;
            grid[r][c] = grid[r + row_num][c] = grid[r][c + col_num] = grid[r + row_num][c + col_num] = ch;
        }
    }

    vector<long long> pow(max(row_num, col_num) + 1);
    pow[0] = 1;
    for (int i = 1; i < (int)pow.size(); i++) pow[i] = mod_mul(pow[i - 1], B);

    vector<vector<long long>> row(col_num, vector<long long>(2 * row_num));
    vector<vector<long long>> col(2 * row_num, vector<long long>(2 * col_num));

    const auto get_hash = [&](const vector<long long> &p_hash, int start, int end) -> long long {
        long long raw_val = (p_hash[end] - mod_mul((start <= 0 ? 0 : p_hash[start]), pow[end - start + 1]) + M) % M;
        return raw_val;
    };

    for (int r = 0; r < 2 * row_num; r++){
        long long curr = 0;
        for (int c = 0; c < 2 * col_num; c++){
            curr = (mod_mul(curr, B) + grid[r][c]) % M;
            col[r][c] = curr;
        }

        for (int c = 0; c < col_num; c++){
            long long prev = (r > 0 ? row[c][r - 1] : 0);
            row[c][r] = (mod_mul(prev, B) + get_hash(col[r], c, c + col_num - 1)) % M;
        }
    }

    int best_r = 0, best_c = 0;
    for (int r = 0; r < row_num; r++){
        for (int c = 0; c < col_num; c++){
            if (get_hash(row[best_c], best_r, best_r + row_num - 1) == get_hash(row[c], r, r + row_num - 1)) continue;

            int low = 0, high = row_num - 1, off = -1;
            while (low <= high){
                int mid = (low + high) / 2;
                bool mis_match = (get_hash(row[best_c], best_r, best_r + mid) != get_hash(row[c], r, r + mid));
                if (mis_match) off = mid, high = mid - 1;
                else low = mid + 1;
            }

            int pos = -1;
            low = 0, high = col_num - 1;
            while (low <= high){
                int mid = (low + high) / 2;
                bool mis_match = (get_hash(col[best_r + off], best_c, best_c + mid) != get_hash(col[r + off], c, c + mid));
                if (mis_match) pos = mid, high = mid - 1;
                else low = mid + 1;
            }

            if (grid[r + off][c + pos] < grid[best_r + off][best_c + pos]){
                best_r = r;
                best_c = c;
            }
        }
    }

    for (int r = 0; r < row_num; r++){
        for (int c = 0; c < col_num; c++){
            cout << grid[best_r + r][best_c + c];
        }
        cout << "\n";
    }

    return 0;
}

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