oj.uz

Submission #763756

# Submission time Handle Problem Language Result Execution time Memory
763756 2023-06-22T18:56:30 Z PanosPask Sateliti (COCI20_satellti) C++14
110 / 110
 1077 ms 49420 KB 
#include <bits/stdc++.h>

using namespace std;

typedef __int128_t lll;
typedef long long ll;

const ll MOD = (1ll << 61) - 1;

const int P = 2;
const int Q = 5;

int n, m;
vector<vector<int>> grid;
vector<vector<ll>> hashed;

vector<ll> pow_q;
vector<ll> pow_p_inv;
vector<ll> pow_q_inv;
vector<ll> pow_p;

pair<int, int> ans = make_pair(0, 0);

ll submatrix(int i1, int j1, int rownum, int colnum)
{
    // The hashing is 1-based
    i1++;
    j1++;

    int i2 = i1 + rownum - 1;
    int j2 = j1 + colnum - 1;
    ll val = hashed[i2][j2] - hashed[i2][j1 - 1] - hashed[i1 - 1][j2] + hashed[i1 - 1][j1 - 1];

    val = ((val % MOD) + MOD) % MOD;

    val = ((lll)val * pow_p[n - i1] % MOD);
    val = ((lll)val * pow_q[m - j1] % MOD);

    return val;
}

// Returns true if the n x m submatrix starting at i1, j1 is smaller than the one starting at i2, j2
bool is_smaller(int i1, int j1, int i2, int j2)
{
    ll a = submatrix(i1, j1, n, m);
    ll b = submatrix(i2, j2, n, m);
    if (a == b) {
        return false;
    }

    int l_row = 0;
    int r_row = n;
    while (r_row > l_row + 1) {
        int mid = (l_row + r_row) / 2;
        if (submatrix(i1, j1, mid, m) == submatrix(i2, j2, mid, m))
            l_row = mid;
        else
            r_row = mid;
    }

    int l_col = 0;
    int r_col = m;
    while (r_col > l_col + 1) {
        int mid = (l_col + r_col) / 2;
        if (submatrix(i1, j1, r_row, mid) == submatrix(i2, j2, r_row, mid))
            l_col = mid;
        else
            r_col = mid;
    }

    return grid[i1 + r_row - 1][j1 + r_col - 1] < grid[i2 + r_row - 1][j2 + r_col - 1];
}

void initialize_hashing(void)
{
    hashed.assign(2 * n + 1, vector<ll>(2 * m + 1, 0));

    for (int i = 0; i < 2 * n; i++)
        for (int j = 0; j < 2 * m; j++) {
            lll h =  hashed[i][j + 1] + hashed[i + 1][j] - hashed[i][j];
            h = ((h % MOD) + MOD) % MOD;

            h += ((lll)grid[i][j] * pow_p[i] % MOD) * (lll)pow_q[j] % MOD;
            h %= MOD;

            hashed[i + 1][j + 1] = h;
        }
}

int main(void)
{
    scanf("%d %d", &n, &m);

    pow_q.resize(2 * m + 1);
    pow_p.resize(2 * n + 1);

    pow_p[0] = pow_q[0] = 1;
    for (int i = 0; i < 2 * n; i++)
        pow_p[i + 1] = (lll)pow_p[i] * P % MOD;
    for (int i = 0; i < 2 * m; i++)
        pow_q[i + 1] = (lll)pow_q[i] * Q % MOD;

    grid.resize(2 * n, vector<int>(2 * m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char c;
            scanf(" %c", &c);

            grid[i][j] = grid[i + n][j] = grid[i][j + m] = grid[i + n][j + m] = (c == '.');
        }

    initialize_hashing();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (is_smaller(i, j, ans.first, ans.second))
                ans = make_pair(i, j);
        }

    for (int i = ans.first; i < ans.first + n; i++) {
        for (int j = ans.second; j < ans.second + m; j++) {
            if (grid[i][j])
                putchar('.');
            else
                putchar('*');
        }
        putchar('\n');
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 77 ms 4512 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 88 ms 4528 KB Output is correct
12 Correct 67 ms 4516 KB Output is correct
13 Correct 81 ms 4660 KB Output is correct
14 Correct 69 ms 4684 KB Output is correct
15 Correct 82 ms 4672 KB Output is correct
16 Correct 72 ms 4680 KB Output is correct
17 Correct 69 ms 4680 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 77 ms 4512 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 88 ms 4528 KB Output is correct
12 Correct 67 ms 4516 KB Output is correct
13 Correct 81 ms 4660 KB Output is correct
14 Correct 69 ms 4684 KB Output is correct
15 Correct 82 ms 4672 KB Output is correct
16 Correct 72 ms 4680 KB Output is correct
17 Correct 69 ms 4680 KB Output is correct
18 Correct 985 ms 49204 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 14 ms 1264 KB Output is correct
21 Correct 1040 ms 49348 KB Output is correct
22 Correct 897 ms 49344 KB Output is correct
23 Correct 1077 ms 49372 KB Output is correct
24 Correct 932 ms 49420 KB Output is correct
25 Correct 1064 ms 49344 KB Output is correct
26 Correct 927 ms 49344 KB Output is correct
27 Correct 901 ms 49232 KB Output is correct