結果
問題 | No.465 PPPPPPPPPPPPPPPPAPPPPPPPP |
ユーザー | pekempey |
提出日時 | 2016-12-17 04:52:37 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 3,434 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 172,364 KB |
実行使用メモリ | 16,192 KB |
最終ジャッジ日時 | 2023-08-20 21:44:22 |
合計ジャッジ時間 | 3,723 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 9 ms
5,688 KB |
testcase_06 | AC | 39 ms
15,580 KB |
testcase_07 | AC | 10 ms
5,632 KB |
testcase_08 | AC | 44 ms
15,116 KB |
testcase_09 | AC | 35 ms
15,468 KB |
testcase_10 | AC | 34 ms
15,584 KB |
testcase_11 | AC | 33 ms
15,256 KB |
testcase_12 | AC | 24 ms
11,944 KB |
testcase_13 | AC | 20 ms
10,112 KB |
testcase_14 | AC | 34 ms
15,900 KB |
testcase_15 | AC | 36 ms
15,664 KB |
testcase_16 | AC | 37 ms
15,276 KB |
testcase_17 | AC | 37 ms
15,436 KB |
testcase_18 | AC | 36 ms
16,000 KB |
testcase_19 | AC | 36 ms
16,020 KB |
testcase_20 | AC | 37 ms
16,192 KB |
testcase_21 | AC | 35 ms
15,888 KB |
32_ratsliveonnoevilstar.txt | AC | 37 ms
16,000 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; class Manacher { private: const string &s; vector<int> rad; vector<int> suf; public: Manacher(const string &s) : s(s), rad(s.size() * 2 - 1), suf(s.size()) { const int n = rad.size(); int i = 0; int j = 0; while (i < n) { while (i - j >= 0 && i + j < n && get(i - j) == get(i + j)) { j++; } rad[i] = j; int k = 1; while (i - k >= 0 && i + k < n && k + rad[i - k] < j) { rad[i + k] = rad[i - k]; k++; } i += k; j -= k; } vector<int> cen(n, n * 3); for (int i = 1; i < n; i++) { int r = min(i - 1, rad[i]); cen[i + r - 1] = min(cen[i + r - 1], i); } for (int i = n - 2; i >= 0; i--) { cen[i] = min(cen[i], cen[i + 1]); } for (int i = 0; i < n; i++) { cen[i] = (i - cen[i]) * 2 + 1; } for (int i = 0; i < s.size(); i++) { suf[i] = (cen[i * 2] + 1) / 2; } } // [l,r) bool isPalindrome(int l, int r) { return rad[l + r - 1] >= r - l; } // [0,k), ignore s[0, k) int longestPalindromicSuffix(int k) { return suf[k - 1]; } private: char get(int k) { return k % 2 == 0 ? s[k / 2] : '+'; } }; vector<int> zAlgorithm(string s) { vector<int> z(s.size()); z[0] = s.size(); int i = 1; int j = 0; while (i < s.size()) { while (i + j < s.size() && s[i + j] == s[j]) { j++; } z[i++] = j; if (j == 0) { continue; } j--; int k = 1; while (i < s.size() && z[k] < j) { z[i++] = z[k++]; j--; } } return z; } int main() { string s; cin >> s; int n = s.size(); Manacher mana(s); vector<bool> bad(n); vector<int64_t> cnt(n + 2); vector<int> z = zAlgorithm(s); for (int i = 1; i < n; i++) { if (bad[i]) { continue; } if (mana.isPalindrome(0, i)) { for (int j = 2; i * j < n; j++) { if (z[i * (j - 1)] < i) { break; } cnt[i * j + 1] += j - 1; bad[i * j] = true; } } } int pre = 1; for (int i = 2; i <= n - 2; i++) { if (!bad[i]) { int suf = mana.longestPalindromicSuffix(i); bool ok = false; if (mana.isPalindrome(0, pre) && mana.isPalindrome(pre, i)) { ok = true; } if (mana.isPalindrome(0, i - suf) && mana.isPalindrome(i - suf, i)) { ok = true; } if (ok) { for (int j = 1; i * j < n; j++) { if (z[i * (j - 1)] < i) { break; } cnt[i * j + 1] += j; bad[i * j] = true; } } } if (mana.isPalindrome(0, i)) { pre = i; } } for (int i = 0; i < n - 1; i++) { cnt[i + 1] += cnt[i]; } int64_t ans = 0; for (int i = 0; i < n; i++) { if (mana.isPalindrome(i, n)) { ans += cnt[i]; } } cout << ans << endl; }