QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557541 | #8668. 回文路径 | Take_A_Single_6 | 0 | 1ms | 15176kb | C++14 | 1.7kb | 2024-09-11 10:13:37 | 2024-09-11 10:13:38 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 1000000007
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
int SS=0,WW=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')WW=-1;
ch = getchar();
}
while(ch>='0'&&ch<='9')
{
SS=(SS<<1)+(SS<<3)+(ch^48);
ch=getchar();
}
return SS*WW;
}
inline void write(int XX)
{
if(XX<0)putchar('-'),XX=-XX;
if(XX>9)write(XX/10);
putchar(XX% 10 + '0');
}
int n,hs1[maxn],hs2[maxn],bs=131,pw[maxn],ans,nxt[maxn];
char s1[maxn],s2[maxn],s[maxn];
int geths1(int l,int r)
{
return hs1[r]-hs1[l-1]*pw[r-l+1];
}
int geths2(int l,int r)
{
return hs2[r]-hs2[l-1]*pw[r-l+1];
}
bool ck1(int l,int r)
{
int len=r-l+1>>1;
if(geths1(l,l+len-1)==geths1(r-len+1,r))return true;
return false;
}
bool ck2(int l,int r)
{
int len=r-l+1>>1;
if(geths2(l,l+len-1)==geths2(r-len+1,r))return true;
return false;
}
signed main()
{
n=read(),cin>>s1+1>>s2+1,pw[0]=1;
for(int i=1;i<=n;i++)hs1[i]=hs1[i-1]*bs+s1[i],pw[i]=pw[i-1]*bs;
for(int i=1;i<=n;i++)hs2[i]=hs2[i-1]*bs+s2[i];
for(int i=n;i;i--)
if(ck1(1,i))
{
ans=i;
break;
}
for(int i=1;i<=n;i++)s[i]=s2[n-i+1];
for(int i=2,j=0;i<=n;i++)
{
while(j&&s1[i]!=s1[j+1])j=nxt[j];
if(s1[i]==s1[j+1])j++;
nxt[i]=j;
}
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=s1[j+1])j=nxt[j];
if(s[i]==s1[j+1])j++;
if(2*j>=i)ans=max(ans,n-i+2);
else if(ck1(j+1,i-j+1)||ck2(j,i-j))ans=max(ans,n-i+2);
}
write(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9700kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
1000
result:
wrong answer 1st lines differ - expected: '6', found: '1000'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 15176kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
1
result:
wrong answer 1st lines differ - expected: '9', found: '1'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%