Submission #714303

#	Time	Username	Problem	Language	Result	Execution time	Memory
714303		Johann	Sateliti (COCI20_satellti)	C++14	110 / 110	989 ms	261280 KiB

Main

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60