oj.uz

Submission #369518

# Submission time Handle Problem Language Result Execution time Memory
369518 2021-02-21T19:37:33 Z wleung_bvg Sateliti (COCI20_satellti) C++17
110 / 110
 626 ms 60104 KB 
#include <bits/stdc++.h>
using namespace std;
template <class C> constexpr int sz(const C &c) { return int(c.size()); }
constexpr const char nl = '\n', sp = ' '; using uint = unsigned int;
using ll = long long; using ull = unsigned long long; using ld = long double;
#if __SIZEOF_INT128__
  using i128 = __int128_t; using ui128 = __uint128_t;
#endif

template <class _T> struct SAISSuffixArray {
  using T = _T;
  static vector<int> SAIS(const vector<int> &S) {
    if (S.empty()) return vector<int>();
    int N = S.size(), K = *max_element(S.begin(), S.end()) + 1;
    vector<bool> isL(N + 1, false); vector<int> ind(N), cnt(K + 1, 0), lms;
    lms.reserve(N); for (auto &&a : S) cnt[a + 1]++;
    partial_sum(cnt.begin(), cnt.end(), cnt.begin());
    isL[N - 1] = true; for (int i = N - 2; i >= 0; i--)
      isL[i] = S[i] == S[i + 1] ? isL[i + 1] : S[i] > S[i + 1];
    auto c = [&] (int i) { return i > 0 && !isL[i] && isL[i - 1]; };
    for (int i = 1; i < N; i++) if (c(i)) lms.push_back(i);
    auto IS = [&] {
      vector<int> tmp(cnt.begin() + 1, cnt.end());
      fill(ind.begin(), ind.end(), -1);
      for (int i = int(lms.size()) - 1; i >= 0; i--)
        ind[--tmp[S[lms[i]]]] = lms[i];
      tmp = vector<int>(cnt.begin(), cnt.end() - 1);
      for (int i = -1, j; i < N; i++)
        if ((j = i < 0 ? N - 1 : ind[i] - 1) >= 0 && isL[j])
          ind[tmp[S[j]]++] = j;
      tmp = vector<int>(cnt.begin() + 1, cnt.end());
      for (int i = N - 1, j; i >= 0; i--)
        if ((j = ind[i] - 1) >= 0 && !isL[j]) ind[--tmp[S[j]]] = j;
    };
    if (int(lms.size()) > 1) {
      IS(); vector<int> tmp(ind.begin(), ind.end());
      for (int i = 0, j = 0, a = -1; i < N; i++) if (c(tmp[i])) {
        for (int b = tmp[i]; a >= 0 && S[a] == S[b];) {
          a++; b++; if (c(a) || c(b)) { j -= int(c(a) && c(b)); break; }
        }
        ind[a = tmp[i]] = ++j;
      }
      tmp = vector<int>(lms.size());
      for (int i = 0; i < int(tmp.size()); i++) tmp[i] = ind[lms[i]];
      tmp = SAIS(tmp);
      for (int i = 0; i < int(tmp.size()); i++) tmp[i] = lms[tmp[i]];
      lms = tmp;
    }
    IS(); return ind;
  }
  static vector<int> init(const vector<T> &S) {
    if (S.empty()) return vector<int>();
    T offset = *min_element(S.begin(), S.end()); vector<int> A(S.size()); 
    for (int i = 0; i < int(S.size()); i++) A[i] = S[i] - offset;
    return A;
  }
  int N; vector<T> S; vector<int> ind, rnk, LCP;
  template <class F> SAISSuffixArray(int N, F f) : N(N) {
    S.reserve(N); for (int i = 0; i < N; i++) S.push_back(f());
    ind = SAIS(init(S)); rnk.resize(N); LCP.resize(N);
    for (int i = 0; i < N; i++) rnk[ind[i]] = i;
    for (int i = 0, k = 0; i < N; i++) {
      if (rnk[i] == N - 1) { LCP[rnk[i]] = k = 0; continue; }
      int j = ind[rnk[i] + 1];
      while (i + k < N && j + k < N && S[i + k] == S[j + k]) k++;
      if ((LCP[rnk[i]] = k) > 0) k--;
    }
  }
  template <class It>
  SAISSuffixArray(It st, It en)
      : SAISSuffixArray(en - st, [&] { return *st++; }) {}
};

template <class It> It minRotation(It st, It en) {
  int N = en - st, i = 0;
  auto ind = [&] (int i) { return i < N ? i : i - N; };
  for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) {
    auto &a = st[ind(i + k)], &b = st[ind(j + k)];
    if (i + k == j || a < b) { j += max(0, k - 1); break; }
    if (a > b) { i = j; break; }
  }
  return st + i;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, M;
  cin >> N >> M;
  vector<string> A(N);
  for (auto &&a : A) cin >> a;
  vector<vector<int>> rnk(N, vector<int>(M)), ind = rnk;
  string S = "";
  S.reserve(N * M * 2);
  for (int i = 0; i < N; i++) {
    S.insert(S.end(), A[i].begin(), A[i].end());
    S.insert(S.end(), A[i].begin(), A[i].end());
  }
  SAISSuffixArray<char> SA(S.begin(), S.end());
  vector<int> sInd(SA.N), r(SA.N);
  for (int i = 0; i < SA.N; i++) {
    if (i != 0 && SA.LCP[i - 1] >= M) sInd[i] = sInd[i - 1];
    else sInd[i] = i;
  }
  for (int i = 0; i < SA.N; i++) r[i] = sInd[SA.rnk[i]];
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
    rnk[i][j] = r[i * M * 2 + j];
    ind[i][SA.ind[SA.rnk[i * M * 2 + j]] % M] = i * M + j;
  }
  vector<pair<vector<int>, int>> rot(M);
  for (int j = 0; j < M; j++) {
    vector<int> col(N);
    for (int i = 0; i < N; i++) col[i] = rnk[i][j];
    auto it = minRotation(col.begin(), col.end());
    int i = it - col.begin();
    rotate(col.begin(), it, col.end());
    rot[j] = make_pair(col, ind[i][j]);
  }
  sort(rot.begin(), rot.end());
  int i = rot[0].second / M, j = rot[0].second % M;
  rotate(A.begin(), A.begin() + i, A.end());
  for (int k = 0; k < N; k++) {
    rotate(A[k].begin(), A[k].begin() + j, A[k].end());
    cout << A[k] << nl;
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 31 ms 5700 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 17 ms 5404 KB Output is correct
12 Correct 17 ms 5400 KB Output is correct
13 Correct 18 ms 5628 KB Output is correct
14 Correct 19 ms 5608 KB Output is correct
15 Correct 21 ms 5608 KB Output is correct
16 Correct 20 ms 5608 KB Output is correct
17 Correct 18 ms 5608 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 31 ms 5700 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 17 ms 5404 KB Output is correct
12 Correct 17 ms 5400 KB Output is correct
13 Correct 18 ms 5628 KB Output is correct
14 Correct 19 ms 5608 KB Output is correct
15 Correct 21 ms 5608 KB Output is correct
16 Correct 20 ms 5608 KB Output is correct
17 Correct 18 ms 5608 KB Output is correct
18 Correct 626 ms 60104 KB Output is correct
19 Correct 5 ms 1148 KB Output is correct
20 Correct 6 ms 1572 KB Output is correct
21 Correct 197 ms 58304 KB Output is correct
22 Correct 186 ms 58304 KB Output is correct
23 Correct 241 ms 58432 KB Output is correct
24 Correct 215 ms 58432 KB Output is correct
25 Correct 362 ms 58428 KB Output is correct
26 Correct 311 ms 58428 KB Output is correct
27 Correct 186 ms 58212 KB Output is correct