結果
問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
ユーザー |
![]() |
提出日時 | 2023-02-03 21:55:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 535 ms / 2,000 ms |
コード長 | 3,989 bytes |
コンパイル時間 | 1,611 ms |
コンパイル使用メモリ | 131,700 KB |
最終ジャッジ日時 | 2025-02-10 09:10:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
// #include <bits/stdc++.h>#include <string.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <ciso646>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define For(i, a, b) for (int i = (int)(a); (i) < (int)(b); ++(i))#define rFor(i, a, b) for (int i = (int)(a)-1; (i) >= (int)(b); --(i))#define rep(i, n) For(i, 0, n)#define rrep(i, n) rFor(i, n, 0)#define fi first#define se second#include <string>#include <vector>namespace rklib {struct RollingHash {private:using ulint = unsigned long long;const ulint hash_mod = (1ULL << 61ULL) - 1, hash_base = 1'000'000'007;const ulint mask_30bit = (1ULL << 30ULL) - 1,mask_31bit = (mask_30bit << 1ULL) + 1;const ulint num = hash_mod << 2LL;std::vector<ulint> pow_table, hash;int n;ulint calc_mul31(ulint a, ulint b) {ulint au = a >> 31ULL, ad = a & mask_31bit;ulint mid = au * b, midu = mid >> 30ULL, midd = mid & mask_30bit;return midu + (midd << 31ULL) + ad * b;}ulint calc_mul61(ulint a, ulint b) {ulint au = a >> 31ULL, ad = a & mask_31bit;ulint bu = b >> 31ULL, bd = b & mask_31bit;ulint mid = au * bd + ad * bu, midu = mid >> 30ULL,midd = mid & mask_30bit;return 2 * au * bu + midu + (midd << 31ULL) + ad * bd;}ulint calc_mod(ulint x) {x = (x & hash_mod) + (x >> 61ULL);if (x > hash_mod) x -= hash_mod;return x;}public:RollingHash(std::string &s) {n = s.size();pow_table.resize(n + 1);hash.resize(n + 1);pow_table[0] = 1ULL;for (int i = 0; i < n; ++i)pow_table[i + 1] = calc_mod(calc_mul61(pow_table[i], hash_base));hash[0] = 0ULL;for (int i = 0; i < n; ++i)hash[i + 1] = calc_mod(calc_mul61(hash[i], hash_base) + s[i]);}ulint slice(int l, int r) {return calc_mod(hash[r] + num - calc_mul61(hash[l], pow_table[r - l]));}};} // namespace rklib#include <algorithm>#include <cassert>#include <vector>namespace rklib {template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <class T>bool chmin_non_negative(T &a, const T &b) {if (a < 0 || a > b) {a = b;return true;}return false;}template <class T>T div_floor(T a, T b) {if (b < 0) a *= -1, b *= -1;return a >= 0 ? a / b : (a + 1) / b - 1;}template <class T>T div_ceil(T a, T b) {if (b < 0) a *= -1, b *= -1;return a > 0 ? (a - 1) / b + 1 : a / b;}} // namespace rklibusing namespace std;using namespace rklib;using lint = long long;using pii = pair<int, int>;using pll = pair<lint, lint>;int main() {string s;cin >> s;int n = s.size();RollingHash rh(s);reverse(s.begin(), s.end());RollingHash rh_rev(s);if (rh.slice(0, n) == rh_rev.slice(0, n)) {printf("%d\n", n);return 0;}int low = 1, high = n;while (high - low > 1) {int mid = (high + low) / 2;bool dp[n + 1];memset(dp, false, sizeof(dp));dp[0] = true;rep(i, n) {if (!dp[i]) continue;For(r, i + mid, n + 1) {if (rh.slice(i, r) == rh_rev.slice(n - r, n - i)) {dp[r] = true;}}}(dp[n] ? low : high) = mid;}printf("%d\n", low);}