QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558022 | #8668. 回文路径 | zhanghuanrui | 0 | 61ms | 8040kb | C++14 | 2.0kb | 2024-09-11 13:30:42 | 2024-09-11 13:30:42 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#ifdef zhr_debug
#define debug printf
#endif
#ifndef zhr_debug
void debug(const char* s,...){}
#endif
using namespace std;
const int bas=521,mod=1000000007;
void freopen(string file){freopen((file+".in").c_str(),"r",stdin);freopen((file+".out").c_str(),"w",stdout);}
char s1[100020],s2[100020];
int n;
int hsh1l[100020],hsh1r[100020];
int hsh2l[100020],hsh2r[100020];
int pw[100020];
int gethsh1l(int l,int r){return (hsh1l[r]-hsh1l[l-1]*pw[r-l+1]%mod+mod)%mod;}
int gethsh2l(int l,int r){return (hsh2l[r]-hsh2l[l-1]*pw[r-l+1]%mod+mod)%mod;}
int gethsh1r(int l,int r){return (hsh1r[l]-hsh1r[r+1]*pw[r-l+1]%mod+mod)%mod;}
int gethsh2r(int l,int r){return (hsh2r[l]-hsh2r[r+1]*pw[r-l+1]%mod+mod)%mod;}
int ans;
void checkodd(int x1,int x2)
{
static int l,r,res,mid;
l=0,r=min(x1-1,n-x2),res=0;
while(l<=r)
{
mid=(l+r)>>1;
if(gethsh1l(x1-mid,x1)==gethsh1r(x2,x2+mid)) res=mid,l=mid+1;
else r=mid-1;
}
ans=max(ans,res*2+1+(x1!=x2));
int ll=x1-res-1,rr=x2+res;
l=0,r=min(ll-1,n-rr),res=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(gethsh1l(ll-mid,ll)==gethsh2r(rr,rr+mid)) res=mid,l=mid+1;
else r=mid-1;
}
ll-=res;rr+=res;
if(res>=0) ans=max(ans,rr-ll+2);
l=0,r=min(x1-1,n-x2),res=0;
while(l<=r)
{
mid=(l+r)>>1;
if(gethsh2l(x1-mid,x1)==gethsh2r(x2,x2+mid)) res=mid,l=mid+1;
else r=mid-1;
}
ans=max(ans,res*2+1+(x1!=x2));
ll=x1-res,rr=x2+res+1;
l=0,r=min(ll-1,n-rr),res=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(gethsh1l(ll-mid,ll)==gethsh2r(rr,rr+mid)) res=mid,l=mid+1;
else r=mid-1;
}
ll-=res;rr+=res;
if(res>=0) ans=max(ans,rr-ll+2);
}
signed main()
{
cin>>n;
scanf("%s%s",s1+1,s2+1);
pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*bas%mod;
for(int i=1;i<=n;i++) hsh1l[i]=(hsh1l[i-1]*bas+s1[i])%mod,hsh2l[i]=(hsh2l[i-1]*bas+s2[i])%mod;
for(int i=n;i>=1;i--) hsh1r[i]=(hsh1r[i+1]*bas+s1[i])%mod,hsh2r[i]=(hsh2r[i+1]*bas+s2[i])%mod;
for(int i=1;i<=n;i++) checkodd(i,i);
for(int i=1;i<n;i++) checkodd(i,i+1);
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 1ms
memory: 5692kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3680kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
8
result:
wrong answer 1st lines differ - expected: '7', found: '8'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 20
Accepted
time: 56ms
memory: 8036kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 61ms
memory: 8040kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 61ms
memory: 7696kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 0
Wrong Answer
time: 56ms
memory: 7704kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%