oj.uz

Submission #498927

# Submission time Handle Problem Language Result Execution time Memory
498927 2021-12-26T18:07:53 Z Victor Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 34628 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 = 2;
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 (prank) cout << "lo = "<<lo<<" hi = "<<hi<<" differ = "<<differ<<endl;
        if (differ)
            hi = mid;
        else
            lo = mid + 1;
    }

    if (prank) {
        //cout << "pos = " << lo << " vals = " << vals[s1 + lo] << ' ' << vals[s2 + lo] << ' ' << hash_val(a, 1, 0, s1) << ' ' << hash_val(b, 1, 0, s2) << endl;
        //cout<<prefix_hash[a][s1 + len - 1][0]<<' '<<(s1 ? prefix_hash[a][s1 - 1][0] : 0)<<endl;
        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;
    // cout << endl;
    while (start < cols) {
        s1 = s2 = start;
        len = cols;
        prank = 0;
        sort(order, order + rows, cmp);
        //rep(i, 0, rows) cout << "row = " << order[i] << ' ' << grid[order[i]].substr(start, cols) << endl;
        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;
            //cout << "s1 = " << s1 << " s2 = " << s2 << endl;
            if (!cmp(rows, rows)) cb_start = row;
        }

        //rep(row, 0, rows * 2) cout << vals[row] << ' ';
        //cout << endl;
        //cout << "shift row = " << cb_start << " shift col = " << start << endl
        //     << endl;

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

        } else {
            // cout << "best_start = " << best_start << " best_start_row = " << best_start_row << endl;
            // cout << "cur_start = " << start << " cur_start_row = " << cb_start << endl;

            prank = 0;
            len = cols;
            rep(row, 0, rows) {
                int a = (best_start_row + row) % rows;
                int b = (cb_start + row) % rows;
                // cout<<"a = "<<a<<" b = "<<b<<endl;
                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;
                }
            }
        }
        // cout << endl;
        ++start;
    }

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 676 KB Output is correct
2 Correct 7 ms 648 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 676 KB Output is correct
2 Correct 7 ms 648 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 629 ms 4556 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 338 ms 4540 KB Output is correct
12 Correct 318 ms 4576 KB Output is correct
13 Correct 346 ms 4692 KB Output is correct
14 Correct 329 ms 4696 KB Output is correct
15 Correct 461 ms 4704 KB Output is correct
16 Correct 515 ms 4684 KB Output is correct
17 Correct 328 ms 4688 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 676 KB Output is correct
2 Correct 7 ms 648 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 629 ms 4556 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 2 ms 1612 KB Output is correct
11 Correct 338 ms 4540 KB Output is correct
12 Correct 318 ms 4576 KB Output is correct
13 Correct 346 ms 4692 KB Output is correct
14 Correct 329 ms 4696 KB Output is correct
15 Correct 461 ms 4704 KB Output is correct
16 Correct 515 ms 4684 KB Output is correct
17 Correct 328 ms 4688 KB Output is correct
18 Execution timed out 3068 ms 34628 KB Time limit exceeded
19 Halted 0 ms 0 KB -