Submission #1165462

#TimeUsernameProblemLanguageResultExecution timeMemory
1165462MPGPalindromic Partitions (CEOI17_palindromic)C++20
100 / 100
339 ms27440 KiB
//#pragma GCC optomize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("O3") //#pragma GCC target("avx2") //#pragma GCC target("sse,sse2,sse4.1,sse4.2") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define max_heap priority_queue<pair <ll, pair <ll, ll>>> #define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> #define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); #define filE freopen("in.txt", "r", stdin);// freopen("out1.txt", "w", stdout); #define endl '\n' #define md(a) (a % mod + mod) % mod #define pb push_back //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //cout << setprecision(5) << fixed << f; //hash prime = 769 ll const maxn = 1e6 + 123; ll const inf = 3e18; ll const loG = 18; // 23 ll const mod = 1e9 + 7; //ll const mod = 998244353; ll const sq = 500; ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;} ll p = 769; ll n, ps[maxn], tav[maxn], inv[maxn]; string s; ll get(ll l, ll r){ ll ret = md(ps[r] - ps[l - 1]); ret = ret * inv[l - 1] % mod; return ret; } void Solve(){ cin >> s; n = s.size(); s = ' ' + s; for (int i = 1; i < n + 1; i++){ ps[i] = (ps[i - 1] + (s[i] - 'a' + 1) * tav[i] % mod) % mod; } ll ans = 0, ind = 0, last = n + 1; bool ok = 1; while (ok){ ok = 0; ind++; if (ind >= last){ break; } //cout << "started " << ind << ' ' << last << endl; for (int i = ind, cnt = 1; i < last; i++, cnt++){ ll x = get(ind, i), y = get(last - cnt, last - 1); //cout << i << ' ' << x << ' ' << y << endl; if (i >= last - cnt) break; if (x == y){ ok = 1; ind = i; last = last - cnt; ans += 2; break; } } if (!ok) ans++; } cout << ans << endl; } int main(){ sariE; //filE; tav[0] = 1; inv[0] = 1; for (int i = 1; i < maxn; i++){ tav[i] = (tav[i - 1] * p) % mod; inv[i] = power(tav[i], mod - 2, mod); } int test = 1; cin >> test; while (test--) Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...