Submission #3337296

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define int long long
using namespace std;
using II = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VII = vector<II>;

class SuffixArray {
public:
  int N;
  string S;
  VI rank; // rank[i]: iから始まるsuffixの辞書順での順位
  VI sorted; // sorted[i]: suffixが辞書順i番目となる開始位置のindex
  SuffixArray(string s) {
    S = s;
    N = S.size();
    sorted = VI(N); rank = VI(N);
    REP (i, N) {
      sorted[i] = i;
      rank[i] = S[i];
    }

    int k;
    function<bool(int, int)> compare_sa = [this, &k](int i, int j) {
      if (rank[i] != rank[j]) { return rank[i] < rank[j]; }
      int ri = i + k < N ? rank[i + k] : -1;
      int rj = j + k < N ? rank[j + k] : -1;
      return ri < rj;
    };

    for (k = 1; k < N; k *= 2) {
      sort(sorted.begin(), sorted.end(), compare_sa);
      VI tmp(N, 0);
      REPI (i, 1, N) {
        tmp[sorted[i]] = tmp[sorted[i - 1]] + compare_sa(sorted[i - 1], sorted[i]);
      }
      rank = tmp;
    }
  }

  // Tが存在する場合はSにおける先頭index, 存在しない場合は-1を返す
  int find(string T) {
    int l = 0, r = N;
    while (r - l > 1) {
      cout << l << endl;
      int mid = (l + r) / 2;
      if (S.compare(sorted[mid], T.size(), T) < 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
    if (S.compare(sorted[l], T.length(), T) != 0) { return -1; }
    return sorted[l];
  }
};

signed main() {
  int K;
  string S;
  cin >> K >> S;
  int N = S.size();
  int part = N / (K + 1);
  int rest = N % (K + 1);
  SuffixArray sf(S);
  if (rest == 0) {
    int ans = 0;
    REP (i, K + 1) {
      if (sf.rank[ans] > sf.rank[part * i]) {
        ans = part * i;
      }
    }
    cout << S.substr(ans, part) << endl;
    return 0;
  }
  int l = -1, r = N - 1;
  while (r - l > 1) {
    int mid = (r + l) / 2;
    int next = 0;
    int adi = 0;
    REP (i, K + 1) {
      if (sf.rank[next] <= sf.rank[sf.sorted[mid]]) {
        next += part + 1;
        adi++;
      } else {
        next += part;
      }
    }
    if (adi >= rest) {
      r = mid;
    } else {
      l = mid;
    }
  }
  cout << S.substr(sf.sorted[r], part + 1) << endl;
}

Submission Info

Judge Result