Submission #3461833


Source Code Expand

Copy
#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 {
  // str: 文字列をintのvectorに直したもの、k: 現れる文字の種類数
  VI sa_is(const VI& str, const int k) {
    const int n = str.size();

    // 0. S, L, LMSを求める
    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--) {
      // Sである条件は、str[i..] < str[i + 1..] (str[i] == str[i + 1]のときは一つ右に依存)
      is_S[i] = str[i] < str[i + 1] || (str[i] == str[i + 1] && is_S[i + 1]);
    }
    REP (i, n) {
      // LMSは一番左のS
      if (is_S[i] & (i == 0 || !is_S[i - 1])) {
        is_LMS[i] = true; LMSs.push_back(i);
      }
    }

    // 1. 適当なLMSの順番でinduced sortする(LMSに注目するとLMS-substringの辞書順になっている)
    VI pseudo_sa = induced_sort(str, LMSs, is_S, k);
    // LMSをsubstringの辞書順に並び替える
    VI orderedLMSs(LMSs.size());
    int index = 0;
    for (int x: pseudo_sa) {
      if (is_LMS[x]) { orderedLMSs[index++] = x; }
    }
    // 隣り合うLMS-substringを比較してrankをつけていく
    pseudo_sa[orderedLMSs[0]] = 0;
    int rank = 0;
    if (orderedLMSs.size() > 1) { pseudo_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; }
      }
      // 同じときは番号をインクリメントしない
      pseudo_sa[orderedLMSs[i + 1]] = is_diff ? ++rank : rank;
    }
    // LMS-substringをひとつのcharとみなしたnew_strを作成
    VI new_str(LMSs.size());
    index = 0;
    REP (i, n) {
      if (is_LMS[i]) { new_str[index++] = pseudo_sa[i]; }
    }

    // 2. 再帰でnew_strのsuffix arrayを求める(これがもとのLMS-substringの辞書順になっている)
    VI LMS_sa;
    if (rank + 1 == LMSs.size()) {
      // LMS-substringの重複がないときは順序そのまま
      LMS_sa = orderedLMSs;
    } else {
      LMS_sa = sa_is(new_str, rank + 1);
      // もとのstrにおけるindexに変換
      for (int& x: LMS_sa) { x = LMSs[x]; }
    }

    // 3. 正しいLMSの順番でinduced sortする(正しいsuffix arrayが得られる)
    return induced_sort(str, LMS_sa, is_S, k);
  }

  // LMS -> L -> M(LMS含む)の順番にbucketに詰めていく、はじめのLMSがprefixについてソートされていれば全てのprefixをソートする正しいアルゴリズム。
  // k: 現れる文字の種類数
  VI induced_sort(const VI& str, const VI& LMSs, const vector<bool>& is_S, const int k) {
    int n = str.size();
    VI buckets(n); // 結果を格納

    // 出現する文字の個数の累積和(各bucketのはじめのindexを表す)
    VI chars(k + 1);
    for (int c: str) { chars[c + 1]++; }
    REP (i, k) { chars[i + 1] += chars[i]; }

    VI count(k); // 各bucketにいくつ入ったか
    // LMSをbucketに後ろから詰める
    for (int i = LMSs.size() - 1; i >= 0; i--) {
      int c = str[LMSs[i]];
      buckets[chars[c + 1] - 1 - count[c]++] = LMSs[i];
    }

    // 昇順、i - 1 がLであったらbucketに前から詰める
    count = VI(k);
    REP (i, n) {
      if (buckets[i] == 0 || is_S[buckets[i] - 1]) { continue; }
      int c = str[buckets[i] - 1];
      buckets[chars[c] + count[c]++] = buckets[i] - 1;
    }

    // 逆順、i - 1 がSであったらbucketに後ろから詰める
    count = VI(k);
    for (int i = n - 1; i >= 0; i--) {
      if (buckets[i] == 0 || !is_S[buckets[i] - 1]) { continue; }
      int c = str[buckets[i] - 1];
      buckets[chars[c + 1] - 1 - count[c]++] = buckets[i] - 1;
    }
    return buckets;
  }
public:
  string S; int N;
  VI sa; // sa[i]: suffixが辞書順i番目となる開始位置のindex
  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] - '$'; }
    sa = sa_is(str, 128);
    sa.erase(sa.begin());
  }
  int operator[](int index) {
    return sa[index];
  }
  // sizeがTと等しく初めてT以上になるようなSの部分文字列(sa)
  VI::iterator lower_bound(string T) {
    int l = -1, r = N;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (S.compare(sa[mid], T.size(), T) < 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
    return sa.begin() + r;
  }

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

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

class LongestCommonPrefix {
  SegTree<> rmq;
public:
  const string S; int N;
  VI sa;
  VI rank; // rank[i]: iから始まるsuffixの辞書順での順位
  VI lcp; // lcp[i]: S[sa[i]..]とS[sa[i + 1]..]が先頭何文字一致しているか、lcp[N - 1] = 0
  VI lcp_begin; // lcp_begin[i]: S[0..]とS[i]が先頭何文字一致しているか
  LongestCommonPrefix();
  LongestCommonPrefix(const string& str) : S(str), N(str.size()), rank(str.size()), lcp(str.size()) {
    sa = SuffixArray(str).sa;
    // rankの設定
    REP (i, N) { rank[sa[i]] = i; }
    // S[i]を順番に見ていきS[i - 1] - 1文字以上が共通することを利用してしゃくとり
    lcp = VI(N);
    int h = 0;
    REP (i, N) {
      if (h > 0) h--;
      if (rank[i] == N - 1) continue;
      int j = sa[rank[i] + 1]; // 比べる対象(辞書順が一つ大きいもの)
      for (; i + h < N && j + h < N; h++) {
        if (S[i + h] != S[j + h]) break;
      }
      lcp[rank[i]] = h;
    }
    // S[i..], S[j..]のlcpが求められるようにRMQ上にのせる
    // rmq = SegTree<int>(lcp, [](int a, int b) { return min(a, b); }, 1e15);
  }
  int operator[](int index) {
    return lcp[index];
  }
  // S[i..], S[j..]が先頭何文字一致しているか
  int query(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);
  }
  void set_lcp_begin() {
    lcp_begin = VI(N);
    lcp_begin[0] = N;
    for (int i = rank[0] - 1; i >= 0; i--) {
      lcp_begin[sa[i]] = min(lcp_begin[sa[i + 1]], lcp[i]);
    }
    for (int i = rank[0] + 1; i < N; i++) {
      lcp_begin[sa[i]] = min(lcp_begin[sa[i - 1]], lcp[i - 1]);
    }
  }
};

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));
  LongestCommonPrefix lcp(w); lcp.set_lcp_begin();
  LongestCommonPrefix lcp_back(w_back); lcp_back.set_lcp_begin();

  vector<bool> is_good(N + 1, true);
  REPI (i, 1, N / 2 + 1) {
    if (!is_good[i]) continue;
    int tmp = lcp.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 = lcp_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 9890 Byte
Status
Exec Time 132 ms
Memory 47468 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_01.txt, example_02.txt, example_03.txt
Subtask1 400 / 400 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 500 / 500 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 1 ms 256 KB
example_02.txt 1 ms 256 KB
example_03.txt 1 ms 256 KB
subtask1_01.txt 1 ms 256 KB
subtask1_02.txt 1 ms 256 KB
subtask1_03.txt 1 ms 384 KB
subtask1_04.txt 1 ms 256 KB
subtask1_05.txt 2 ms 512 KB
subtask1_06.txt 2 ms 512 KB
subtask1_07.txt 1 ms 256 KB
subtask1_08.txt 2 ms 640 KB
subtask1_09.txt 2 ms 640 KB
subtask1_10.txt 2 ms 640 KB
subtask1_11.txt 2 ms 640 KB
subtask1_12.txt 2 ms 640 KB
subtask1_13.txt 2 ms 640 KB
subtask1_14.txt 2 ms 640 KB
subtask1_15.txt 1 ms 256 KB
subtask1_16.txt 1 ms 256 KB
subtask1_17.txt 1 ms 256 KB
subtask1_18.txt 1 ms 256 KB
subtask1_19.txt 2 ms 640 KB
subtask1_20.txt 2 ms 640 KB
subtask1_21.txt 2 ms 640 KB
subtask1_22.txt 2 ms 640 KB
subtask1_23.txt 2 ms 640 KB
subtask1_24.txt 2 ms 640 KB
subtask1_25.txt 2 ms 640 KB
subtask1_26.txt 2 ms 640 KB
subtask1_27.txt 2 ms 640 KB
subtask1_28.txt 2 ms 640 KB
subtask1_29.txt 2 ms 640 KB
subtask1_30.txt 2 ms 640 KB
subtask1_31.txt 2 ms 640 KB
subtask1_32.txt 2 ms 640 KB
subtask1_33.txt 2 ms 640 KB
subtask2_01.txt 112 ms 35264 KB
subtask2_02.txt 3 ms 1172 KB
subtask2_03.txt 59 ms 37400 KB
subtask2_04.txt 58 ms 37400 KB
subtask2_05.txt 3 ms 1172 KB
subtask2_06.txt 59 ms 37496 KB
subtask2_07.txt 59 ms 37496 KB
subtask2_08.txt 104 ms 47468 KB
subtask2_09.txt 102 ms 47468 KB
subtask2_10.txt 123 ms 47468 KB
subtask2_11.txt 100 ms 47468 KB
subtask2_12.txt 132 ms 47160 KB
subtask2_13.txt 83 ms 47420 KB
subtask2_14.txt 82 ms 47420 KB
subtask2_15.txt 73 ms 44792 KB
subtask2_16.txt 72 ms 44792 KB
subtask2_17.txt 72 ms 44792 KB
subtask2_18.txt 72 ms 44792 KB
subtask2_19.txt 60 ms 37496 KB
subtask2_20.txt 77 ms 45796 KB
subtask2_21.txt 76 ms 44072 KB
subtask2_22.txt 71 ms 37496 KB
subtask2_23.txt 71 ms 37496 KB
subtask2_24.txt 96 ms 39776 KB
subtask2_25.txt 88 ms 41544 KB
subtask2_26.txt 131 ms 42892 KB
subtask2_27.txt 108 ms 37836 KB
subtask2_28.txt 61 ms 24068 KB
subtask2_29.txt 82 ms 35976 KB