QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558246 | #8668. 回文路径 | ccccccyd | 0 | 15ms | 10188kb | C++14 | 2.1kb | 2024-09-11 15:03:47 | 2024-09-11 15:03:48 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ph push_back
#define mk make_pair
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(int i(r),i##end(l);i>=i##end;--i)
using namespace std;
const int N=1e5+20;
int n,d[N<<1]; char a[N<<1]; vector<pair<int,int> > qry;
void manache(char str[]){
int tn=n<<1|1;
rep(i,1,tn) a[i]=(i&1)?'*':str[i>>1];
int x=0;
rep(i,1,tn){
if(x+d[x]>i) d[i]=min(x+d[x]-i,d[x-(i-x)]);
while(i-d[i]-1>0&&a[i-d[i]-1]==a[i+d[i]+1]) d[i]++;
if(i+d[i]>x+d[x]) x=i;
if(d[i]) qry.ph(mk((i-d[i])/2+1,(i+d[i])/2));
}
}
const ll base0=1737,mod0=1e9+9,base1=2333,mod1=998244353;
int ans; char s[N],t[N]; ll ss0[N],st0[N],g0[N]={1},ss1[N],st1[N],g1[N]={1};
int solve(const int l,const int r){
int lf=1,rg=min(l-1,n-r+1),m,k=0;
while(lf<=rg){
m=(lf+rg)>>1;
if(((ss0[l-1]-ss0[l-1-m]*g0[m])-(st0[r]-st0[r+m]*g0[m]))%mod0==0
&&((ss1[l-1]-ss1[l-1-m]*g1[m])-(st1[r]-st1[r+m]*g1[m]))%mod1==0)
k=m,lf=m+1;
else rg=m-1;
}
// printf("%d %d %d %d %d\n",l,r,lf,rg,k);
return r-l+1+k*2;
}
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%s%s",&n,s+1,t+1);
rep(i,1,n) g0[i]=g0[i-1]*base0%mod0;
rep(i,1,n) g1[i]=g1[i-1]*base1%mod1;
rep(i,1,n) ss0[i]=(ss0[i-1]*base0+s[i]-'a')%mod0;
per(i,n,1) st0[i]=(st0[i+1]*base0+t[i]-'a')%mod0;
rep(i,1,n) ss1[i]=(ss1[i-1]*base1+s[i]-'a')%mod1;
per(i,n,1) st1[i]=(st1[i+1]*base1+t[i]-'a')%mod1;
manache(s);
for(auto x:qry) ans=max(ans,solve(x.first,x.second));//,printf("%d %d %d\n",x.first,x.second,ans);
rep(i,1,n) ans=max(ans,solve(i+1,i));
cerr<<ans<<'\n';
reverse(s+1,s+n+1),reverse(t+1,t+n+1);
rep(i,1,n) ss0[i]=(ss0[i-1]*base0+s[i]-'a')%mod0;
per(i,n,1) st0[i]=(st0[i+1]*base0+t[i]-'a')%mod0;
rep(i,1,n) ss1[i]=(ss1[i-1]*base1+s[i]-'a')%mod1;
per(i,n,1) st1[i]=(st1[i+1]*base1+t[i]-'a')%mod1;
qry.clear(),manache(s);
for(auto x:qry) ans=max(ans,solve(x.first,x.second));//,printf("%d %d %d\n",x.first,x.second,ans);
rep(i,1,n) ans=max(ans,solve(i+1,i));
cout<<ans;
return 0;
}//g++ -g P4324.cpp -o my -std=c++14 -Wextra
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 0ms
memory: 5832kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 1ms
memory: 3984kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 5940kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
238
result:
wrong answer 1st lines differ - expected: '28', found: '238'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 15ms
memory: 10188kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
12
result:
wrong answer 1st lines differ - expected: '9', found: '12'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%