# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516286 | fcmalkcin | Palindromic Partitions (CEOI17_palindromic) | C++17 | 20 ms | 15968 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.
/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define F(i,a,b) for (ll i=a;i<=b;i++)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=1e6+40;
const ll mod=1000003 ;
const ll base=317;
/// you will be the best but now you just are trash
/// goal 2/7
ll a[maxn];
struct tk
{
ll mod;
ll n;
string s;
ll f[maxn];
ll mu[maxn];
tk()
{
memset(mu,0,sizeof(mu));
ll h=5e8;
while (1)
{
ll nw=((abs)((ll)rnd()))%h +h ;
bool chk=true;
for (ll i=2;i*i<=nw;i++)
{
if (nw%i==0)
{
chk=false;
break;
}
}
if (chk)
{
mod=nw;
break;
}
}
mu[0]=1;
for (int i=1;i<maxn;i++)
{
mu[i]=(mu[i-1]*base)%mod;
}
}
void init(string s)
{
ll n=s.length();
f[0]=0;
for (int i=1;i<=n;i++)
{
f[i]=(f[i-1]*base+s[i-1]-'a'+1)%mod;
}
}
ll get(ll l,ll r)
{
return ((f[r]-f[l-1]*mu[r-l+1])%mod+mod)%mod;
}
}man,man1;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll t;
cin>> t;
while (t--)
{
string s;
cin>> s;
ll n=s.length();
man.init(s);
man1.init(s);
ll ans=0;
for (int i=1;i<=n/2+1;i++)
{
ll j=i;
while (j<=(n/2)+1&&make_pair(man.get(i,j),man1.get(i,j))!=make_pair(man.get(n-j+1,n-i+1),man1.get(n-j+1,n-i+1)))
{
j++;
}
if (j>(n/2))
{
ans++;
break;
}
else
{
ans+=2;
// cout <<i<<" "<<j<<endl;
i=j;
}
}
cout <<ans<<endl;
}
}
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... |