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