제출 #679862

#제출 시각아이디문제언어결과실행 시간메모리
679862peijarPalindromic Partitions (CEOI17_palindromic)C++17
60 / 100
10037 ms31204 KiB
#include <bits/stdc++.h> #define int long long using namespace std; namespace std { template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) { out << "["; for (int i = 0; i < (int)vec.size(); ++i) { out << vec[i]; if (i + 1 < (int)vec.size()) out << ", "; } return out << "]"; } } // namespace std void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif template <const int32_t MOD> struct ModInt { int32_t x; ModInt() : x(0) {} ModInt(long long u) : x(u % MOD) { if (x < 0) x += MOD; } friend bool operator==(const ModInt &a, const ModInt &b) { return a.x == b.x; } friend bool operator!=(const ModInt &a, const ModInt &b) { return a.x != b.x; } friend bool operator<(const ModInt &a, const ModInt &b) { return a.x < b.x; } friend bool operator>(const ModInt &a, const ModInt &b) { return a.x > b.x; } friend bool operator<=(const ModInt &a, const ModInt &b) { return a.x <= b.x; } friend bool operator>=(const ModInt &a, const ModInt &b) { return a.x >= b.x; } static ModInt sign(long long k) { return ((k & 1) ? ModInt(MOD - 1) : ModInt(1)); } ModInt &operator+=(const ModInt &m) { x += m.x; if (x >= MOD) x -= MOD; return *this; } ModInt &operator-=(const ModInt &m) { x -= m.x; if (x < 0LL) x += MOD; return *this; } ModInt &operator*=(const ModInt &m) { x = (1LL * x * m.x) % MOD; return *this; } friend ModInt operator-(const ModInt &a) { ModInt res(a); if (res.x) res.x = MOD - res.x; return res; } friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += ModInt(b); } friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= ModInt(b); } friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= ModInt(b); } static long long fp(long long u, long long k) { long long res = 1LL; while (k > 0LL) { if (k & 1LL) res = (res * u) % MOD; u = (u * u) % MOD; k /= 2LL; } return res; } static constexpr int mod() { return MOD; } ModInt fastpow(long long k) { return ModInt(fp(x, k)); } ModInt inv() { assert(x); return ModInt(fp(x, MOD - 2)); } ModInt &operator/=(const ModInt &m) { return *this *= ModInt(m).inv(); } friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) *= ModInt(b).inv(); } friend ostream &operator<<(ostream &out, const ModInt &a) { return out << a.x; } friend istream &operator>>(istream &in, ModInt &a) { return in >> a.x; } }; const int MOD1 = 1e9 + 9, MOD2 = 1e9 + 7; template <typename T1, typename T2> struct ModPair { T1 x; T2 y; ModPair() : x(0), y(0) {} ModPair(int u) : x(u), y(u) {} ModPair(T1 _x, T2 _y) : x(_x), y(_y) {} ModPair &operator+=(const ModPair &other) { x += other.x; y += other.y; return *this; } ModPair &operator*=(const ModPair &other) { x *= other.x; y *= other.y; return *this; } ModPair &operator-=(const ModPair &other) { x -= other.x; y -= other.y; return *this; } friend ModPair operator+(const ModPair &a, const ModPair &b) { return ModPair(a) += ModPair(b); } friend ModPair operator-(const ModPair &a, const ModPair &b) { return ModPair(a) -= ModPair(b); } friend ModPair operator*(const ModPair &a, const ModPair &b) { return ModPair(a) *= ModPair(b); } bool operator<(const ModPair &o) const { return pair(x, y) < pair(o.x, o.y); } bool operator>(const ModPair &o) const { return pair(x, y) > pair(o.x, o.y); } bool operator<=(const ModPair &o) const { return pair(x, y) <= pair(o.x, o.y); } bool operator>=(const ModPair &o) const { return pair(x, y) >= pair(o.x, o.y); } bool operator==(const ModPair &o) const { return pair(x, y) == pair(o.x, o.y); } ModPair inv() { return ModPair(x.inv(), y.inv()); }; }; using H = ModPair<ModInt<MOD1>, ModInt<MOD2>>; const int BASE = 311; struct Hashes { vector<H> po, pref, invPo; Hashes(string s) { int n = s.size(); po.resize(n); invPo.resize(n); pref.resize(n + 1); po[0] = 1; for (int i = 1; i < n; ++i) po[i] = po[i - 1] * BASE; invPo[n - 1] = po[n - 1].inv(); for (int i = n - 1; i > 0; --i) invPo[i - 1] = invPo[i] * BASE; for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + po[i] * s[i]; } H getHsh(int deb, int fin) { return (pref[fin] - pref[deb]) * invPo[deb]; } }; void solve() { string s; cin >> s; int N = s.size(); if (N == 1) { cout << 1 << '\n'; return; } dbg(s, N); string L = s.substr(0, N / 2); string R = s.substr((N + 1) / 2, N / 2); Hashes hashL(L), hashR(R); dbg(L, R); vector<int> dp(N / 2 + 1); dp[0] = N % 2; for (int lft = 1; lft <= N / 2; ++lft) { dp[lft] = 1; for (int take = 1; take <= lft; ++take) if (hashL.getHsh(N / 2 - lft, N / 2 - lft + take) == hashR.getHsh(lft - take, lft)) dp[lft] = max(dp[lft], dp[lft - take] + 2); } cout << dp[N / 2] << '\n'; } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbTests; cin >> nbTests; for (int iTest(0); iTest < nbTests; ++iTest) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...