Submission #369518

#	Time	Username	Problem	Language	Result	Execution time	Memory
369518		wleung_bvg	Sateliti (COCI20_satellti)	C++17	110 / 110	626 ms	60104 KiB

Main

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