oj.uz

Submission #714303

# Submission time Handle Problem Language Result Execution time Memory
714303 2023-03-24T08:16:51 Z Johann Sateliti (COCI20_satellti) C++14
110 / 110
 989 ms 261280 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<pii> vpii;
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()

const ll MOD = ((1LL << 61) - 1);
const ll P = 9973;
const ll P1 = 98999;
const ll P2 = 22573;
const ll P3 = 1367;
const ll P4 = 41809;

ll mod_mul(ll a, ll b)
{
    __int128 res = (__int128)a * b;
    return res % MOD;
}

int N, M; // N := #Rows, M := #Coloumns
void shift(int y, int x, int amount, int &yn, int &xn)
{
    xn = x + amount;
    yn = y + xn / M;
    xn = xn % M;
    yn = yn % N;
}
vvi grid;
vvvi dpRow; // DP within rows
vvvi dpCol; // DP within cols
vi pot;
int logheight;

ll liftRow(int y, int x, int amount)
{
    ll res = 0;
    for (int i = logheight - 1; i >= 0; --i)
        if (amount & (1 << i))
        {
            res = (mod_mul(pot[1 << i], res) + dpRow[y][x][i]) % MOD;
            x = (x + (1 << i)) % M;
        }
    return res;
}
void makeDP()
{
    logheight = max(ceil(log2(M) + 1), ceil(log2(N) + 1));
    pot.assign(max(N, M) * (1 << logheight) + 5, 1LL); // pot[i] = P^i
    for (int l = 1; l < sz(pot); ++l)
        pot[l] = mod_mul(P, pot[l - 1]);

    // DP within Rows
    dpRow.assign(N, vvi(M, vi(logheight, 0)));
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            dpRow[y][x][0] = grid[y][x];
    for (int j = 1; j < logheight; ++j)
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < M; ++x)
                dpRow[y][x][j] = (mod_mul(pot[1 << (j - 1)], dpRow[y][x][j - 1]) + dpRow[y][(x + (1 << (j - 1))) % M][j - 1]) % MOD;

    // Spalten
    dpCol.assign(N, vvi(M, vi(logheight, 0)));
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            dpCol[y][x][0] = liftRow(y, x, M);
    for (int j = 1; j < logheight; ++j)
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < M; ++x)
                dpCol[y][x][j] = (mod_mul(pot[M * (1 << (j - 1))], dpCol[y][x][j - 1]) + dpCol[(y + (1 << (j - 1))) % N][x][j - 1]) % MOD;
}

bool compare(int y1, int x1, int y2, int x2)
{
    for (int j = logheight - 1; j >= 0; --j)
        if (dpCol[y1][x1][j] == dpCol[y2][x2][j])
        {
            y1 = (y1 + (1 << j)) % N;
            y2 = (y2 + (1 << j)) % N;
        }
    for (int j = logheight - 1; j >= 0; --j)
        if (dpRow[y1][x1][j] == dpRow[y2][x2][j])
        {
            x1 = (x1 + (1 << j)) % M;
            x2 = (x2 + (1 << j)) % M;
        }
    return grid[y1][x1] < grid[y2][x2];
}

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

    cin >> N >> M;

    grid.assign(N, vi(M, 0));
    for (int i = 0; i < N; ++i)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < M; ++j)
            grid[i][j] = tmp[j];
    }

    makeDP();

    int xmin = 0, ymin = 0;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            if (compare(y, x, ymin, xmin))
                ymin = y, xmin = x;

    for (int dy = 0; dy < N; ++dy)
    {
        for (int dx = 0; dx < M; ++dx)
            cout << (char)grid[(ymin + dy) % N][(xmin + dx) % M];
        cout << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 724 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 63 ms 23992 KB Output is correct
9 Correct 6 ms 3412 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 61 ms 23996 KB Output is correct
12 Correct 69 ms 24180 KB Output is correct
13 Correct 67 ms 24772 KB Output is correct
14 Correct 77 ms 24728 KB Output is correct
15 Correct 64 ms 24776 KB Output is correct
16 Correct 67 ms 24780 KB Output is correct
17 Correct 80 ms 24772 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 63 ms 23992 KB Output is correct
9 Correct 6 ms 3412 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 61 ms 23996 KB Output is correct
12 Correct 69 ms 24180 KB Output is correct
13 Correct 67 ms 24772 KB Output is correct
14 Correct 77 ms 24728 KB Output is correct
15 Correct 64 ms 24776 KB Output is correct
16 Correct 67 ms 24780 KB Output is correct
17 Correct 80 ms 24772 KB Output is correct
18 Correct 989 ms 260444 KB Output is correct
19 Correct 38 ms 18800 KB Output is correct
20 Correct 41 ms 21004 KB Output is correct
21 Correct 810 ms 261176 KB Output is correct
22 Correct 854 ms 261276 KB Output is correct
23 Correct 728 ms 261196 KB Output is correct
24 Correct 834 ms 261156 KB Output is correct
25 Correct 722 ms 261176 KB Output is correct
26 Correct 803 ms 261280 KB Output is correct
27 Correct 854 ms 260648 KB Output is correct