Submission #1078657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078657		SansPapyrus683	Sateliti (COCI20_satellti)	C++17	110 / 110	481 ms	96852 KiB

Main

#include <iostream>
#include <vector>
#include <cassert>

using std::cout;
using std::endl;
using std::vector;
using std::pair;

constexpr char CRATER = '*';
constexpr char EMPTY = '.';
constexpr int MOD = 1e9 + 7;

long long pow(long long base, long long exp, long long mod) {
    assert(exp >= 0);
    base %= exp;
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % mod;
        }
        base = base * base % mod;
        exp /= 2;
    }
    return res;
}

long long mod_inv(long long n, long long mod) { return pow(n, mod - 2, mod); }

/**
 * https://evaluator.hsin.hr/tasks/HONI202135sateliti/
 * (sample input omitted due to length)
 */
int main() {
    int row_num;
    int col_num;
    std::cin >> row_num >> col_num;

    vector<long long> pow2((row_num * 2) * (col_num * 2));
    vector<long long> pow2_mod_invs(pow2.size());
    pow2[0] = pow2_mod_invs[0] = 1;
    long long base_inv = mod_inv(2, MOD);
    for (int p = 1; p < pow2.size(); p++) {
        pow2[p] = pow2[p - 1] * 2 % MOD;
        pow2_mod_invs[p] = (pow2_mod_invs[p - 1] * base_inv) % MOD;
    }

    vector<vector<bool>> times2(row_num * 2, vector<bool>(col_num * 2));
    for (int r = 0; r < row_num; r++) {
        for (int c = 0; c < col_num; c++) {
            char cell;
            std::cin >> cell;
            times2[r][c] = times2[r + row_num][c + col_num] = cell != CRATER;
            times2[r + row_num][c] = times2[r][c + col_num] = cell != CRATER;
        }
    }
    
    vector<vector<long long>> pref_vals(
        times2.size() + 1, vector<long long>(times2[0].size() + 1)
    );
    for (int r = 0; r < times2.size(); r++) {
        for (int c = 0; c < times2[r].size(); c++) {
            // don't think overflow would happen
            pref_vals[r + 1][c + 1] = (
                pref_vals[r + 1][c]
                + pref_vals[r][c + 1]
                - pref_vals[r][c]
                + times2[r][c] * pow2[r * (2 * col_num) + c]
            );
        }
    }

    auto sum_rect = [&] (int sr, int sc, int er, int ec) {
        return (
            pref_vals[er + 1][ec + 1] + pref_vals[sr][sc]
            - pref_vals[sr][ec + 1] - pref_vals[er + 1][sc]
        );
    };
    auto hash = [&] (int r, int c, int square_num) {
        int row_amt = square_num / col_num;
        long long total = 0;
        if (row_amt > 0) {
            total += sum_rect(r, c, r + row_amt - 1, c + col_num - 1);
        }
        if (square_num % col_num > 0) {
            int rem = square_num % col_num;
            total += sum_rect(r + row_amt, c, r + row_amt, c + rem - 1);
        }
        return total % MOD * pow2_mod_invs[r * (2 * col_num) + c] % MOD;
    };

    pair<int, int> best{0, 0};
    for (int sr = 0; sr < row_num; sr++) {
        for (int sc = 0; sc < col_num; sc++) {
            if (sr == 0 && sc == 0) {
                continue;
            }

            int lo = 0;
            int hi = row_num * col_num;
            int eq_chars = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                long long best_hash = hash(best.first, best.second, mid);
                long long this_hash = hash(sr, sc, mid);
                if (best_hash == this_hash) {
                    eq_chars = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            int dr = eq_chars / col_num;
            int dc = eq_chars % col_num;
            if (times2[sr + dr][sc + dc] < times2[best.first + dr][best.second + dc]) {
                best = {sr, sc};
            }
        }
    }

    for (int r = 0; r < row_num; r++) {
        for (int c = 0; c < col_num; c++) {
            cout << (times2[best.first + r][best.second + c] ? EMPTY : CRATER);
        }
        cout << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int p = 1; p < pow2.size(); p++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int r = 0; r < times2.size(); r++) {
      |                     ~~^~~~~~~~~~~~~~~
Main.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int c = 0; c < times2[r].size(); c++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

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