QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558963 | #8668. 回文路径 | Chendaqian | 0 | 104ms | 8488kb | C++14 | 1.5kb | 2024-09-11 19:28:54 | 2024-09-11 19:28:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const long long P=11451419198102353,bs=31;
int n;
char s[2][N];
long long pw[N];
long long sumpre[2][N],sumsuf[2][N];
int ans;
long long getpre(int co,int l,int r) {
return (sumpre[co][r]+P-(__int128_t)sumpre[co][l-1]*pw[r-l+1]%P)%P;
}
long long getsuf(int co,int l,int r) {
return (sumsuf[co][l]+P-(__int128_t)sumsuf[co][r+1]*pw[r-l+1]%P)%P;
}
int calc(int c1,int s1,int c2,int s2) {
int l=1,r=min(s1,n-s2+1),res=0;
while(l<=r) {
int mid=(l+r)/2;
if(getpre(c1,s1-mid+1,s1)==getsuf(c2,s2,s2+mid-1))
res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
int main() {
cin>>n>>(s[0]+1)>>(s[1]+1);
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*bs%P;
for(int j=0;j<2;j++) {
for(int i=1;i<=n;i++) {
sumpre[j][i]=(sumpre[j][i-1]*bs+s[j][i]-'a')%P;
}
for(int i=n;i>=1;i--) {
sumsuf[j][i]=(sumsuf[j][i+1]*bs+s[j][i]-'a')%P;
}
}
for(int i=1;i<=n;i++) {
int p=calc(0,i,0,i),res=calc(0,i-p,1,i+p-1);
ans=max(ans,res*2+p*2-1);
}
for(int i=1;i<n;i++) if(s[0][i]==s[0][i+1]) {
int p=calc(0,i,0,i+1),res=calc(0,i-p,1,i+p);
ans=max(ans,res*2+p*2);
}
for(int i=1;i<=n;i++) ans=max(ans,calc(0,i,1,i)*2);
for(int i=1;i<=n;i++) {
int p=calc(1,i,1,i),res=calc(0,i-p+1,1,i+p);
ans=max(ans,res*2+p*2-1);
}
for(int i=1;i<n;i++) if(s[1][i]==s[1][i+1]) {
int p=calc(1,i,1,i+1),res=calc(0,i-p+1,1,i+p+1);
ans=max(ans,res*2+p*2);
}
cout<<ans<<"\n";
return 0;
}
/*
cd PKUSC2024D1T1
g++ code.cpp -o code -std=c++14 -O2 -Wall -static
./code
*/
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: 5896kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
0
result:
wrong answer 1st lines differ - expected: '6', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 104ms
memory: 8488kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
0
result:
wrong answer 1st lines differ - expected: '9', found: '0'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%