oj.uz

Submission #498929

# Submission time Handle Problem Language Result Execution time Memory
498929 2021-12-26T18:09:45 Z Victor Sateliti (COCI20_satellti) C++17
110 / 110
 2835 ms 20076 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

const ll modulo[] = {INF, INF + 2}, bases[] = {1337, 4269}, num_bases = 1;
string grid[1001];
int rows, cols;
ll base_pow[num_bases][2001], prefix_hash[1001][2001][num_bases];

int hash_val(int row, int len, int base, int start) { return ((prefix_hash[row][start + len - 1][base] - (start ? prefix_hash[row][start - 1][base] : 0) * base_pow[base][len]) % modulo[base] + modulo[base]) % modulo[base]; }

int start = 0, s1, s2, len;
bool prank;
int order[1001], vals[2001];
bool cmp(const int &a, const int &b) {
    int lo = 0, hi = len;
    while (lo != hi) {
        int mid = (lo + hi) / 2;
        bool differ = 0;
        rep(base, 0, num_bases) differ |= hash_val(a, mid + 1, base, s1) != hash_val(b, mid + 1, base, s2);

        if (differ)
            hi = mid;
        else
            lo = mid + 1;
    }

    if (prank) {
        return vals[s1 + lo] < vals[s2 + lo];

    } else
        return grid[a][s1 + lo] < grid[b][s2 + lo];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    rep(i, 0, num_bases) {
        base_pow[i][0] = 1;
        rep(j, 1, 2001) base_pow[i][j] = base_pow[i][j - 1] * bases[i] % modulo[i];
    }

    cin >> rows >> cols;
    rep(row, 0, rows) {
        cin >> grid[row];
        grid[row].append(grid[row]);
        rep(col, 0, cols * 2) rep(base, 0, num_bases) prefix_hash[row][col][base] = ((col ? prefix_hash[row][col - 1][base] : 0) * bases[base] + grid[row][col]) % modulo[base];
    }

    rep(i, 0, rows) order[i] = i;

    int best_start = -1, best_start_row;
    while (start < cols) {
        s1 = s2 = start;
        len = cols;
        prank = 0;
        sort(order, order + rows, cmp);
        int pos = 0;
        rep(row, 0, rows) {
            if (row) {
                bool differ = 0;
                rep(base, 0, num_bases) differ |= hash_val(order[row], cols, base, start) != hash_val(order[row - 1], cols, base, start);
                pos += differ;
            }
            vals[order[row]] = vals[order[row] + rows] = pos;
        }

        rep(row, 0, rows * 2) rep(base, 0, num_bases) prefix_hash[rows][row][base] = ((row ? prefix_hash[rows][row - 1][base] : 0) * bases[base] + vals[row % rows]) % modulo[base];

        prank = 1;
        len = rows;
        int cb_start = 0;
        rep(row, 0, rows) {
            s1 = cb_start;
            s2 = row;
            if (!cmp(rows, rows)) cb_start = row;
        }

        if (best_start == -1) {
            best_start = start;
            best_start_row = cb_start;

        } else {

            prank = 0;
            len = cols;
            rep(row, 0, rows) {
                int a = (best_start_row + row) % rows;
                int b = (cb_start + row) % rows;
                s1 = best_start;
                s2 = start;

                bool differ = 0;
                rep(base, 0, num_bases) differ |= hash_val(a, len, base, s1) != hash_val(b, len, base, s2);
                if (differ) {
                    if (!cmp(a, b)) {
                        best_start = start;
                        best_start_row = cb_start;
                    }
                    break;
                }
            }
        }
        ++start;
    }

    rep(i, 0, rows) {
        rep(j, 0, cols) cout << grid[(i + best_start_row) % rows][(j + best_start) % cols];
        cout << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:26: warning: 'best_start_row' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     int best_start = -1, best_start_row;
      |                          ^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 584 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 584 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 161 ms 3084 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 92 ms 3072 KB Output is correct
12 Correct 106 ms 3124 KB Output is correct
13 Correct 94 ms 3168 KB Output is correct
14 Correct 88 ms 3172 KB Output is correct
15 Correct 126 ms 3164 KB Output is correct
16 Correct 153 ms 3148 KB Output is correct
17 Correct 92 ms 3180 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 584 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 161 ms 3084 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 92 ms 3072 KB Output is correct
12 Correct 106 ms 3124 KB Output is correct
13 Correct 94 ms 3168 KB Output is correct
14 Correct 88 ms 3172 KB Output is correct
15 Correct 126 ms 3164 KB Output is correct
16 Correct 153 ms 3148 KB Output is correct
17 Correct 92 ms 3180 KB Output is correct
18 Correct 2710 ms 18984 KB Output is correct
19 Correct 13 ms 4556 KB Output is correct
20 Correct 18 ms 732 KB Output is correct
21 Correct 1659 ms 19976 KB Output is correct
22 Correct 1614 ms 19980 KB Output is correct
23 Correct 1736 ms 19980 KB Output is correct
24 Correct 1795 ms 19984 KB Output is correct
25 Correct 2423 ms 19984 KB Output is correct
26 Correct 2835 ms 20076 KB Output is correct
27 Correct 1562 ms 19964 KB Output is correct