#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,rs,f[nmax],x,t;
ll p[]={31,67},m[]={1000003,1000000007},pw[2][nmax],in[2][nmax],hs[2][nmax];
string s;
ll bn(ll x,ll p,ll md)
{
if(x==1)return 1;
ll rs=1;
while(p)
{
if(p&1LL)rs=(rs*x)%md;
x=(x*x)%md;
p>>=1LL;
}
return rs;
}
bool eq(int L,int R,int A,int B)
{
ll x[2][2];
int l[2],r[2];
l[0]=L,l[1]=A,r[0]=R,r[1]=B;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
x[i][j]=hs[j][r[i]];
if(l[i])x[i][j]=(x[i][j]-hs[j][l[i]-1]+m[j])%m[j];
x[i][j]=(x[i][j]*in[j][l[i]])%m[j];
}
}
for(int i=0;i<2;i++)if(x[0][i]!=x[1][i])return 0;
return 1;
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
for(j=0;j<2;j++)
{
in[j][0]=1;
in[j][1]=bn(p[j],m[j]-2,m[j]);
}
for(i=2;i<=1e6;i++)for(j=0;j<2;j++)in[j][i]=(in[j][i-1]*p[j])%m[j];
cin>>t;
while(t--)
{
cin>>s;
n=s.size();
for(i=0;i<n;i++)
{
if(i==0)
{
for(j=0;j<1;j++)
{
pw[j][i]=1;
hs[j][i]=s[i];
}
}
else
{
for(j=0;j<1;j++)
{
pw[j][i]=(pw[j][i-1]*p[j])%m[j];
hs[j][i]=(hs[j][i-1]+pw[j][i]*s[i])%m[j];
}
}
}
rs=0;
j=0;
for(i=0;i<n/2;i++)
{
if(eq(j,i,n-i-1,n-j-1))
{
rs++;
j=i+1;
}
}
rs*=2;
if(n%2==1 || j<n/2)rs++;
cout<<rs<<endl;
}
return 0;
}
Compilation message
palindromic.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
palindromic.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
15992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
15992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
15992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
15992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
