oj.uz

Submission #1078657

# Submission time Handle Problem Language Result Execution time Memory
1078657 2024-08-28T03:16:49 Z SansPapyrus683 Sateliti (COCI20_satellti) C++17
110 / 110
 481 ms 96852 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 28 ms 8796 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 33 ms 8796 KB Output is correct
12 Correct 39 ms 8804 KB Output is correct
13 Correct 28 ms 9048 KB Output is correct
14 Correct 34 ms 9096 KB Output is correct
15 Correct 28 ms 9052 KB Output is correct
16 Correct 31 ms 9048 KB Output is correct
17 Correct 33 ms 9052 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 28 ms 8796 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 33 ms 8796 KB Output is correct
12 Correct 39 ms 8804 KB Output is correct
13 Correct 28 ms 9048 KB Output is correct
14 Correct 34 ms 9096 KB Output is correct
15 Correct 28 ms 9052 KB Output is correct
16 Correct 31 ms 9048 KB Output is correct
17 Correct 33 ms 9052 KB Output is correct
18 Correct 415 ms 96596 KB Output is correct
19 Correct 3 ms 1624 KB Output is correct
20 Correct 6 ms 2136 KB Output is correct
21 Correct 451 ms 96852 KB Output is correct
22 Correct 460 ms 96852 KB Output is correct
23 Correct 391 ms 96848 KB Output is correct
24 Correct 462 ms 96848 KB Output is correct
25 Correct 389 ms 96852 KB Output is correct
26 Correct 477 ms 96828 KB Output is correct
27 Correct 481 ms 96740 KB Output is correct