QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561376 | #8668. 回文路径 | hhiron | 20 | 20ms | 12736kb | C++14 | 1.3kb | 2024-09-12 22:03:57 | 2024-09-12 22:03:58 |
Judging History
answer
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define int long long
#define ull unsigned long long
typedef long long ll;
using namespace std;
//const int MOD=547567998244353;
const int N=5e5+5;
int n,l,r,len[N];
ull po[N];
ull has1l[N],has1r[N],has2l[N],has2r[N];
string s1,s2;
ull gethash(int x,int y,ull *a){
return (a[y]-a[x]*po[abs(y-x)]);
}
int ans=0;
void solve(){
for(int i=1;i<=n;i++) has1l[i]=(has1l[i-1]*131+s1[i]);
for(int i=1;i<=n;i++) has2l[i]=(has2l[i-1]*131+s2[i]);
for(int i=n;i>=1;i--) has1r[i]=(has1r[i+1]*131+s1[i]);
for(int i=n;i>=1;i--) has2r[i]=(has2r[i+1]*131+s2[i]);
// cout<<s1<<endl;
for(int i=1;i<=n;i++){
int l=0,r=min(n-i+1,i);
while(r-l>1){
int mid=(l+r)>>1;
if(gethash(i-mid,i+mid,has1l)==gethash(i+mid,i-mid,has1r)) l=mid;
else r=mid;
}int poil=i-r-1,poir=i+r;
ans=max(ans,l*2+1);
l=0,r=min(poil-1,n-poir);
if(s1[poil]!=s2[poir]) continue;
// while(r-l>1){
// int mid=(l+r)>>1;
// if(gethash(mid))
// }
}
}
signed main(){
cin>>n>>s1>>s2;
s1=" "+s1; s2=" "+s2;
po[0]=1;
for(int i=1;i<=n;i++) po[i]=po[i-1]*131;
solve();
swap(s1,s2);
for(int i=1;i<=n/2;i++) swap(s1[i],s1[n-i+1]);
for(int i=1;i<=n/2;i++) swap(s2[i],s2[n-i+1]);
solve();
printf("%lld",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: 7932kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
5
result:
wrong answer 1st lines differ - expected: '6', found: '5'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 19ms
memory: 9220kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 19ms
memory: 9284kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 19ms
memory: 12736kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 19ms
memory: 11196kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 20ms
memory: 12680kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%