QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558029#8668. 回文路径zhanghuanrui30 35ms7984kbC++142.4kb2024-09-11 13:35:262024-09-11 13:35:26

Judging History

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

  • [2024-09-11 13:35:26]
  • 评测
  • 测评结果:30
  • 用时:35ms
  • 内存:7984kb
  • [2024-09-11 13:35:26]
  • 提交

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;
	if(s1[x1]==s1[x2])
	{
		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);
	}
	if(s2[x1]==s2[x2])
	{
		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));
		int 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);
	}
}
void checkmid(int x)
{
	if(s1[x]!=s2[x]) return;
	static int l,r,mid,res;
	l=0,r=min(x-1,n-x),res=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(gethsh1l(x-mid,x)==gethsh2r(x,x+mid)) res=mid,l=mid+1;
		else r=mid-1;
	}
	ans=max(ans,mid*2+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);
	for(int i=1;i<=n;i++) checkmid(i);
	cout<<ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 30
Accepted

Test #1:

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

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

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

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

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

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

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

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

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

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

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

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

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

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

36

result:

ok single line: '36'

Test #9:

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

input:

1000
aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...

output:

50

result:

ok single line: '50'

Test #10:

score: 30
Accepted
time: 0ms
memory: 3628kb

input:

1000
aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...

output:

20

result:

ok single line: '20'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 32ms
memory: 7688kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 35ms
memory: 7656kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 35ms
memory: 7764kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Wrong Answer
time: 31ms
memory: 7984kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

10

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%