oj.uz

답안 #498928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498928 2021-12-26T18:09:10 Z Victor Sateliti (COCI20_satellti) C++17
50 / 110
 3000 ms 33740 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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 588 KB Output is correct
2 Correct 8 ms 644 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 8 ms 588 KB Output is correct
6 Correct 7 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 588 KB Output is correct
2 Correct 8 ms 644 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 8 ms 588 KB Output is correct
6 Correct 7 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 664 ms 4452 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 321 ms 4448 KB Output is correct
12 Correct 333 ms 4492 KB Output is correct
13 Correct 344 ms 4592 KB Output is correct
14 Correct 348 ms 4588 KB Output is correct
15 Correct 463 ms 4588 KB Output is correct
16 Correct 512 ms 4592 KB Output is correct
17 Correct 348 ms 4600 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 588 KB Output is correct
2 Correct 8 ms 644 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 8 ms 588 KB Output is correct
6 Correct 7 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 664 ms 4452 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 321 ms 4448 KB Output is correct
12 Correct 333 ms 4492 KB Output is correct
13 Correct 344 ms 4592 KB Output is correct
14 Correct 348 ms 4588 KB Output is correct
15 Correct 463 ms 4588 KB Output is correct
16 Correct 512 ms 4592 KB Output is correct
17 Correct 348 ms 4600 KB Output is correct
18 Execution timed out 3080 ms 33740 KB Time limit exceeded
19 Halted 0 ms 0 KB -