QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558009 | #8668. 回文路径 | DaiRuiChen007 | 0 | 34ms | 7976kb | C++17 | 1.8kb | 2024-09-11 13:28:06 | 2024-09-11 13:28:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5;
mt19937_64 rnd(time(0));
int n,ans=0;
char s[2][MAXN];
ull B,hw[26],pw[MAXN],hs[2][MAXN],rs[2][MAXN];
ull qhs(ull *h,int l,int r) { return h[r]-h[l-1]*pw[r-l+1]; }
ull qrs(ull *h,int l,int r) { return qhs(h,n-r+1,n-l+1); }
bool judge(int l,int k,int r) {
return qhs(hs[0],l,k)*pw[r-k+1]+qhs(hs[1],k,r)==qrs(rs[1],k,r)*pw[k-l+1]+qrs(rs[0],l,k);
}
void solve() {
for(int i=1;i<=n;++i) { //center = i
int L=0,R=min(i-1,n-i),x=0,y=0;
while(L<=R) {
int t=(L+R)>>1;
if(judge(i-t,i+t,i+t-1)) x=t,L=t+1;
else R=t-1;
}
L=0,R=min(i-x-1,n-i-x+1);
while(L<=R) {
int t=(L+R)>>1;
if(judge(i-x-t,i+x,i+x+t-1)) y=t,L=t+1;
else R=t-1;
}
ans=max(ans,2*(x+y)+1);
}
for(int i=1;i<n;++i) if(s[0][i]==s[0][i+1]) { //center = i,i+1
int L=0,R=min(i,n-i),x=0,y=0;
while(L<=R) {
int t=(L+R)>>1;
if(judge(i+1-t,i+t,i+t-1)) x=t,L=t+1;
else R=t-1;
}
L=0,R=min(i-x,n-i-x+1);
while(L<=R) {
int t=(L+R)>>1;
if(judge(i+1-x-t,i+x,i+x+t-1)) y=t,L=t+1;
else R=t-1;
}
ans=max(ans,2*(x+y));
}
for(int i=1;i<=n;++i) if(s[0][i]==s[1][i]) { //center = i,i
int L=0,R=min(i,n-i+1),x=0;
while(L<=R) {
int t=(L+R)>>1;
if(judge(i-x+1,i,i+x-1)) x=t,L=t+1;
else R=t-1;
}
ans=max(ans,2*x);
}
}
signed main() {
scanf("%d%s%s",&n,s[0]+1,s[1]+1),B=rnd()|1;
for(int c=0;c<26;++c) hw[c]=rnd()|1;
for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*B;
for(int o:{0,1}) {
for(int i=1;i<=n;++i) {
hs[o][i]=hs[o][i-1]*B+hw[s[o][i]-'a'];
rs[o][i]=rs[o][i-1]*B+hw[s[o][n-i+1]-'a'];
}
}
solve();
swap(s[0],s[1]),swap(hs[0],rs[1]),swap(hs[1],rs[0]);
reverse(s[0]+1,s[0]+n+1),reverse(s[1]+1,s[1]+n+1);
solve();
printf("%d\n",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: 0ms
memory: 7348kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
496
result:
wrong answer 1st lines differ - expected: '6', found: '496'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 34ms
memory: 7976kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
49988
result:
wrong answer 1st lines differ - expected: '9', found: '49988'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%