Submission #3389287


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>;

template <class T = int>
class SegTree {
  using VT = vector<T>;
  int orig_n;
  // k番目のノードの[l, r)について[a, b)を求める
  T query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) { return UNIT; }
    if (a <= l && r <= b) { return dat[k]; }
    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return f(vl, vr);
  }
public:
  int N;
  VT dat;
  function<T(T, T)> f;
  int UNIT;
  SegTree(int n, function<T(T, T)> f_, const T unit) {
    orig_n = n;
    f = f_;
    UNIT = unit;
    for (N = 1; N < n; N *= 2);
    dat = VT(2 * N - 1, UNIT);
  }
  SegTree(VT a = {}, function<T(T, T)> f_ = [](int a, int b) { return min(a, b); }, T unit = 1e15) {
    orig_n = a.size();
    f = f_;
    UNIT = unit;
    for (N = 1; N < a.size(); N *= 2);
    dat = VT(2 * N - 1);
    REP (i, a.size()) {
      dat[N - 1 + i] = a[i];
    }
    for (int k = N - 2; k >= 0; k--) {
      dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  // k番目をaに
  void update(int k, int a) {
    k += N - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  // [a, b)でのクエリ
  T query(int a, int b) {
    assert(0 <= a && a < b && b <= orig_n);
    return query(a, b, 0, 0, N);
  }
};

class SuffixArray {
  SegTree<> rmq;
  VI induced_sort(VI str, VI LMSs, vector<bool> is_S, int k) {
    int n = str.size();
    VI sa(n);
    // 出現する文字の個数の累積和で各bucketのindex
    VI chars(k + 1);
    for (int c: str) { chars[c + 1]++; }
    REP (i, k) { chars[i + 1] += chars[i]; }
    assert(chars[k] == str.size());
    // 各bucketにいくつ入ったか
    VI count(k);
    // LMSをbucketに後ろから詰める
    for (int i = LMSs.size() - 1; i >= 0; i--) {
      int c = str[LMSs[i]];
      sa[chars[c + 1] - 1 - count[c]++] = LMSs[i];
    }
    // 昇順、i - 1 がLであったらbucketに前から詰める
    count = VI(k);
    REP (i, n) {
      if (sa[i] == 0 || is_S[sa[i] - 1]) { continue; }
      int c = str[sa[i] - 1];
      sa[chars[c] + count[c]++] = sa[i] - 1;
    }
    // 逆順、i - 1 がSであったらbucketに後ろから詰める
    count = VI(k);
    for (int i = n - 1; i >= 0; i--) {
      if (sa[i] == 0 || !is_S[sa[i] - 1]) { continue; }
      int c = str[sa[i] - 1];
      sa[chars[c + 1] - 1 - count[c]++] = sa[i] - 1;
    }
    return sa;
  }

  // k: 入力文字の種類
  VI sa_is(VI str, int k) {
    VI sa;
    const int n = str.size();
    vector<bool> is_S(n); is_S[n - 1] = true;
    vector<bool> is_LMS(n);
    VI LMSs;
    for (int i = n - 2; i >= 0; i--) {
      is_S[i] = str[i] < str[i + 1] || (str[i] == str[i + 1] && is_S[i + 1]);
    }
    REP (i, n) {
      if (is_S[i] & (i == 0 || !is_S[i - 1])) {
        is_LMS[i] = true; LMSs.push_back(i);
      }
    }
    sa = induced_sort(str, LMSs, is_S, k);
    // LMSをsubstringの辞書順に並び替える
    VI orderedLMSs(LMSs.size());
    int index = 0;
    for (int x: sa) {
      if (is_LMS[x]) { orderedLMSs[index++] = x; }
    }
    assert(index == orderedLMSs.size());
    // 隣り合うLMS-substringを比較する
    sa[orderedLMSs[0]] = 0;
    int rank = 0;
    if (orderedLMSs.size() > 1) { sa[orderedLMSs[1]] = ++rank; }
    REPI (i, 1, orderedLMSs.size() - 1) {
      bool is_diff = false;
      REP (j, n) {
        int p = orderedLMSs[i] + j;
        int q = orderedLMSs[i + 1] + j;
        if (str[p] != str[q] || is_LMS[p] != is_LMS[q]) {
          is_diff = true; break;
        }
        if (j > 0 && is_LMS[p]) {
          assert(is_LMS[q]);
          break;
        }
      }
      // 同じときは番号をインクリメントしない
      sa[orderedLMSs[i + 1]] = is_diff ? ++rank : rank;
    }
    VI new_str(LMSs.size());
    index = 0;
    REP (i, n) {
      if (is_LMS[i]) { new_str[index++] = sa[i]; }
    }
    // LMS-suffixの辞書順を求める
    VI LMS_sa;
    if (rank + 1 == LMSs.size()) {
      // 重複がないときはLMS-substringの順序そのまま
      LMS_sa = orderedLMSs;
    } else {
      LMS_sa = sa_is(new_str, rank + 1);
      for (int& x: LMS_sa) { x = LMSs[x]; }
    }
    return induced_sort(str, LMS_sa, is_S, k);
  }
  void set_lcp() {
    // S[i]を順番に見ていきS[i - 1] - 1文字以上が共通することを利用してしゃくとり
    lcp_next_rank = VI(N);
    int h = 0;
    REP (i, N) {
      if (h > 0) h--;
      if (rank[i] == N - 1) continue;
      int j = sorted[rank[i] + 1]; // 比べる対象(辞書順が一つ大きいもの)
      for (; i + h < N && j + h < N; h++) {
        if (S[i + h] != S[j + h]) break;
      }
      lcp_next_rank[rank[i]] = h;
    }
    // S[i..], S[j..]のlcpが求められるようにRMQ上にのせる
    // rmq = SegTree<int>(lcp_next_rank, [](int a, int b) { return min(a, b); }, 1e15);
  }
public:
  int N;
  string S;
  VI rank; // rank[i]: iから始まるsuffixの辞書順での順位
  VI sorted; // sorted[i]: suffixが辞書順i番目となる開始位置のindex
  VI lcp_next_rank; // lcp[i]: S[sorted[i]..]とS[sorted[i + 1]..]が先頭何文字一致しているか、lcp[N - 1] = 0
  VI lcp_begin;
  // 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;
  //   }
  SuffixArray(string str_in) : S(str_in), N(str_in.size()) {
    str_in += "$";
    VI str(N + 1);
    REP (i, N + 1) {
      str[i] = str_in[i] - '$';
    }
    sorted = sa_is(str, 128);
    sorted.erase(sorted.begin());
    rank = VI(N);
    REP (i, N) {
      rank[sorted[i]] = i;
    }
    set_lcp();
    set_lcp_begin();
  }
  void set_lcp_begin() {
    lcp_begin = VI(N);
    lcp_begin[0] = N;
    for (int i = rank[0] - 1; i >= 0; i--) {
      lcp_begin[sorted[i]] = min(lcp_begin[sorted[i + 1]], lcp_next_rank[i]);
    }
    for (int i = rank[0] + 1; i < N; i++) {
      lcp_begin[sorted[i]] = min(lcp_begin[sorted[i - 1]], lcp_next_rank[i - 1]);
    }
  }

  // sizeがTと等しく初めてT以上になるようなSの部分文字列(sortedのイテレータを返す)
  VI::iterator lower_bound(string T) {
    int l = -1, r = N;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (S.compare(sorted[mid], T.size(), T) < 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
    return sorted.begin() + r;
  }

  // sizeがTと等しく初めてTより大きくなるようなSの部分文字列(sortedのイテレータを返す)
  VI::iterator upper_bound(string T) {
    int l = -1, r = N;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (S.compare(sorted[mid], T.size(), T) <= 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
    return sorted.begin() + r;
  }

  // S2が部分文字列として何回出現するか
  int count(string S2) {
    return upper_bound(S2) - lower_bound(S2);
  }

  // S[i..], S[j..]が先頭何文字一致しているか
  int lcp(int i, int j) {
    assert(0 <= i && 0 <= j && i < N && j < N);
    if (i == j) return N - i;
    int l = min(rank[i], rank[j]);
    int r = max(rank[i], rank[j]);
    return rmq.query(l, r);
  }
};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  string w; cin >> w;
  int N = w.size();
  int same = true;
  REP (i, N - 1) {
    if (w[i] != w[i + 1]) same = false;
  }
  if (same) {
    cout << N << endl << 1 << endl; return 0;
  }

  string w_back;
  reverse_copy(w.begin(), w.end(), back_inserter(w_back));
  SuffixArray sa(w);
  SuffixArray sa_back(w_back);

  vector<bool> is_good(N + 1, true);
  REPI (i, 1, N / 2 + 1) {
    if (!is_good[i]) continue;
    int tmp = sa.lcp_begin[i];
    for (int j = 2; i * (j - 1) <= tmp; j++) {
      is_good[i * j] = false;
    }
  }
  vector<bool> rev_is_good(N + 1, true);
  REPI (i, 1, N / 2 + 1) {
    if (!rev_is_good[i]) continue;
    int tmp = sa_back.lcp_begin[i];
    for (int j = 2; i * (j - 1) <= tmp; j++) {
      rev_is_good[i * j] = false;
    }
  }

  if (is_good[N]) {
    cout << 1 << endl << 1 << endl; return 0;
  }

  int cnt = 0;
  REPI (i, 1, N) {
    if (is_good[i] && rev_is_good[N - i]) cnt++;
  }
  cout << 2 << endl << cnt << endl;
}

Submission Info

Submission Time
Task F - Best Representation
User knshnb
Language C++14 (GCC 5.4.1)
Score 900
Code Size 9449 Byte
Status AC
Exec Time 164 ms
Memory 51920 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 500 / 500
Status
AC × 3
AC × 36
AC × 65
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt
All example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 1 ms 256 KB
example_02.txt AC 1 ms 256 KB
example_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 384 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 2 ms 640 KB
subtask1_06.txt AC 2 ms 640 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 2 ms 640 KB
subtask1_09.txt AC 2 ms 640 KB
subtask1_10.txt AC 2 ms 640 KB
subtask1_11.txt AC 2 ms 640 KB
subtask1_12.txt AC 2 ms 640 KB
subtask1_13.txt AC 2 ms 640 KB
subtask1_14.txt AC 2 ms 640 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 2 ms 640 KB
subtask1_20.txt AC 2 ms 640 KB
subtask1_21.txt AC 2 ms 640 KB
subtask1_22.txt AC 2 ms 640 KB
subtask1_23.txt AC 2 ms 640 KB
subtask1_24.txt AC 2 ms 640 KB
subtask1_25.txt AC 2 ms 640 KB
subtask1_26.txt AC 2 ms 640 KB
subtask1_27.txt AC 2 ms 640 KB
subtask1_28.txt AC 2 ms 640 KB
subtask1_29.txt AC 2 ms 640 KB
subtask1_30.txt AC 2 ms 640 KB
subtask1_31.txt AC 2 ms 640 KB
subtask1_32.txt AC 2 ms 640 KB
subtask1_33.txt AC 2 ms 640 KB
subtask2_01.txt AC 112 ms 39256 KB
subtask2_02.txt AC 3 ms 1172 KB
subtask2_03.txt AC 65 ms 41412 KB
subtask2_04.txt AC 66 ms 41412 KB
subtask2_05.txt AC 3 ms 1172 KB
subtask2_06.txt AC 65 ms 41504 KB
subtask2_07.txt AC 64 ms 41504 KB
subtask2_08.txt AC 148 ms 49256 KB
subtask2_09.txt AC 148 ms 49256 KB
subtask2_10.txt AC 151 ms 49256 KB
subtask2_11.txt AC 148 ms 49256 KB
subtask2_12.txt AC 164 ms 47384 KB
subtask2_13.txt AC 87 ms 51920 KB
subtask2_14.txt AC 87 ms 51920 KB
subtask2_15.txt AC 78 ms 49768 KB
subtask2_16.txt AC 77 ms 49768 KB
subtask2_17.txt AC 77 ms 49768 KB
subtask2_18.txt AC 77 ms 49768 KB
subtask2_19.txt AC 65 ms 41504 KB
subtask2_20.txt AC 81 ms 50912 KB
subtask2_21.txt AC 84 ms 50180 KB
subtask2_22.txt AC 71 ms 41504 KB
subtask2_23.txt AC 96 ms 41504 KB
subtask2_24.txt AC 120 ms 42828 KB
subtask2_25.txt AC 109 ms 41304 KB
subtask2_26.txt AC 125 ms 47700 KB
subtask2_27.txt AC 147 ms 38128 KB
subtask2_28.txt AC 62 ms 24608 KB
subtask2_29.txt AC 88 ms 40700 KB