# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
468964 | wdjpng | Palindromic Partitions (CEOI17_palindromic) | C++17 | 314 ms | 19192 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
vector<int>powr(1e6+1);
int mod = 1e9+7;
int solve(string s)
{
int n = s.size();
int maxx = 1;
int c = 0;
int s1 = 0;
int s2 = 0;
rep(i,n)
{
if(i>=n-1-i) continue;
s1=26*s1+s[i]-'a';
s2+=powr[c]*(s[n-i-1]-'a');
s1%=mod;
s2%=mod;
//cout<<s1<<" "<<s2<<"\n";
c++;
if(s1==s2)
{
s1=0;
s2=0;
c=0;
int cur = 2*(maxx/2) + 2;
if(i+1!=n-1-i) cur++;
maxx = cur;
}
}
return maxx;
}
signed main()
{
int t;
cin>>t;
powr[0]=1;
for(int i = 1; i<powr.size();i++) powr[i]=26*powr[i-1]%mod;
while (t--)
{
string s;
cin>>s;
cout << solve(s) <<"\n";
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |