QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562706 | #8668. 回文路径 | hhiron | 20 | 78ms | 17812kb | C++14 | 1.4kb | 2024-09-13 20:10:38 | 2024-09-13 20:10:39 |
Judging History
answer
#include<bits/stdc++.h>
#define INF 0x7fffffff
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=5e5+5;
int n;
ull has1l[N],has2l[N],has1r[N],po[N];
string a,b,s1,s2;
inline ull gethash(int x,int y,ull *has){
return (has[y]-has[x]*po[abs(x-y)]);
}int ans=0;
void solve(){
has1l[0]=s1[0]-'a',has2l[0]=s2[0]-'a';
// cout<<s1<<endl<<s2<<endl;
for(int i=1;i<=n+1;i++) has1l[i]=has1l[i-1]*31+s1[i]-'a';
for(int i=n+1;i>=0;i--) has1r[i]=has1r[i+1]*31+s1[i]-'a';
for(int i=1;i<=n+1;i++) has2l[i]=has2l[i-1]*31+s2[i]-'a';
for(int i=1;i<=n;i++){
int l=0,r=min(n,n-i)+1;
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 lrc=(l*2+1)/2;
int posl=i-l-1,posr=i+l-1;
int kkk=0;
while(s1[posl-kkk]==s2[posr+kkk]) kkk++;
l=0,r=min(posl,n-posr)+1;
while(r-l>1){
int mid=(l+r)>>1;
if(gethash(posl,posl-mid,has1r)==gethash(posr,posr+mid,has2l)) l=mid;
else r=mid;
}
ans=max(ans,lrc+(s1[posl]==s2[posr]));
// cout<<i<<" "<<s1[i]<<" "<<l<<endl;
}
}
int main(){
cin>>n>>a>>b;
po[0]=1;
for(int i=1;i<=n*4;i++) po[i]=po[i-1]*31;
a=" "+a;
b=" "+b;
s1+='?',s2+='-';
for(int i=1;i<=n;i++){
s1+='#',s2+='#';
s1+=a[i],s2+=b[i];
}s1+='#',s2+='#',s1+='~',s2+='@';
n=n*2+1;
solve();
swap(s1,s2);
reverse(s1.begin(),s1.end()); reverse(s2.begin(),s2.end());
solve();
cout<<ans;
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 2ms
memory: 7736kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 7792kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
4
result:
wrong answer 1st lines differ - expected: '7', found: '4'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 76ms
memory: 15724kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 78ms
memory: 17608kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 73ms
memory: 17620kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 77ms
memory: 17812kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 60ms
memory: 17544kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%