제출 #1205905

#제출 시각아이디문제언어결과실행 시간메모리
1205905friendiksPalindromic Partitions (CEOI17_palindromic)C++20
0 / 100
16 ms15936 KiB
#ifndef LOCAL #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC diagnostic ignored "-Wpedantic" #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rnd(52); template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename V> using table = gp_hash_table<T, V>; using i128 = __int128; using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; const ll INF = 2e18; const int inf = 2e9; const int maxn = 1e6; const int MOD = 1e9 + 7; const ld pi = acos(-1); const int P = 5167; const int L = 26; const ld EPS = 1e-7; template<typename T, typename V> void fill(T &container, V value) { for (auto &c: container) c = value; } #define int ll int ps[maxn]; int backps[maxn]; string get_str(int l, int r, string&s) { string res; for (int i = l-1; i < r; ++i) res += s[i]; return res; } int cnt(int l, int r, string&s) { int mx = 1; for (int len = 1; 2 * len <= r - l + 1; ++len) { if (get_str(l, l + len - 1, s) == get_str(r - len + 1, r, s)) { mx = max(mx, 2 + cnt(l + len, r - len, s)); } } return mx; } int bp(int a, int n) { int res = 1; while (n) { if (n & 1) { res *= a; res %= MOD; } a *= a; a %= MOD; n /= 2; } return res; } void solve() { string s; cin >> s; int n = s.size(); cout << cnt(1, n, s) << "\n"; } signed main() { ps[0] = 1; for (int i = 1; i < maxn; ++i) ps[i] = (ps[i - 1] * P) % MOD; backps[maxn - 1] = bp(ps[maxn - 1], MOD - 2); for (int i = maxn - 1; i > 0; --i) backps[i - 1] = (backps[i] * P) % MOD; #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(4); int t = 1; cin >> t; while (t--) solve(); //stress(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...