QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558264 | #8668. 回文路径 | syp11 | 0 | 7ms | 18732kb | C++14 | 1.2kb | 2024-09-11 15:13:28 | 2024-09-11 15:13:29 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=1e6+10;
const int B=13;
int n,res,pl[N];
ull pw[N],hsa[N],hsb[N];
char a[N],b[N];
void solve(char *a,char *b)
{
pw[0]=1;
hsa[0]=a[0];
for(int i=1;i<=n;i++)
{
pw[i]=pw[i-1]*B;
pl[i]=0;
}
for(int i=1;i<=n+1;i++)
{
hsa[i]=hsa[i-1]*B+a[i];
}
for(int i=n+1;i>=0;i--)
{
hsb[i]=hsb[i+1]*B+b[i];
}
for(int i=1,md=0,r=0;i<=n;i++)
{
if(i<=r)
{
pl[i]=min(pl[2*md-i],r-i+1);
}
while(a[i-pl[i]]==a[i+pl[i]])
{
pl[i]++;
}
if(i+pl[i]>r)
{
r=i+pl[i]-1;
md=i;
}
}
for(int i=1;i<=n;i++)
{
int p=max(res,pl[i]);
for(;p<=i;p++)
{
ull x=hsa[i-pl[i]]-hsa[i-p-1]*pw[p-pl[i]+1];
ull y=hsb[i+pl[i]-2]-hsb[i+p-1]*pw[p-pl[i]+1];
if(x!=y)
{
break;
}
}
res=max(res,p);
}
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
a[0]=b[0]='@';
for(int i=1;i<=n;i++)
{
cin>>a[2*i];
a[2*i-1]='#';
}
for(int i=1;i<=n;i++)
{
cin>>b[2*i];
b[2*i-1]='#';
}
n<<=1;
a[n+1]=b[n+1]='#';
solve(a,b);
reverse(a+2,a+n+1);
reverse(b+2,a+n+1);
solve(b,a);
cout<<res-1<<flush;
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: 2ms
memory: 10772kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 0ms
memory: 11804kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 11940kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
40
result:
wrong answer 1st lines differ - expected: '28', found: '40'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 20
Accepted
time: 7ms
memory: 17152kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 0ms
memory: 18732kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 0
Wrong Answer
time: 4ms
memory: 18708kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
10
result:
wrong answer 1st lines differ - expected: '11', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%