Submission #318056

#TimeUsernameProblemLanguageResultExecution timeMemory
318056soroushPalindromic Partitions (CEOI17_palindromic)C++14
0 / 100
1 ms364 KiB
/* #pragma GCC optimize("O2") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,fma,tune=native") //*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int ,int > pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn = 3e6; const ll mod =1e9+7; const ld PI = acos((ld)-1); #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} string s; int q; vector < int > kmp(string s){ int n = s.size(); vector < int > f(n); for(int i = 1; i < n ; i ++){ int j = f[i-1]; while(j and s[i]!=s[j]) j = f[j-1]; j+=(s[i]==s[j]) , f[i] = j; } return(f); } int solve(string s){ vector < int > f = kmp(s); int n = s.size(); if(n==0)return(0); if(f[n-1] == 0)return(1); string res = ""; for(int i = f[n-1] ; i < n-f[n-1] ; i ++){ res+=s[i]; } return(2 + solve(res)); } int32_t main(){ migmig; cin >> q; while(q -- ){ cin >> s; cout << solve(s) << endl; } 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...