QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562691#8668. 回文路径hhiron0 27ms21160kbC++141.5kb2024-09-13 20:03:422024-09-13 20:03:42

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 20:03:42]
  • 评测
  • 测评结果:0
  • 用时:27ms
  • 内存:21160kb
  • [2024-09-13 20:03:42]
  • 提交

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],has2r[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=n+1;i>=0;i--) has2r[i]=has2r[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=-1,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+kkk);
//		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;
}

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: 7976kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 30
Accepted
time: 1ms
memory: 7748kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

score: 30
Accepted
time: 1ms
memory: 7848kb

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 7812kb

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

26

result:

wrong answer 1st lines differ - expected: '27', found: '26'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 27ms
memory: 21160kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 21ms
memory: 20556kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Wrong Answer
time: 21ms
memory: 20440kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

9

result:

wrong answer 1st lines differ - expected: '11', found: '9'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%