QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558011#8668. 回文路径zhanghuanrui0 61ms7768kbC++142.0kb2024-09-11 13:28:162024-09-11 13:28:16

Judging History

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

  • [2024-09-11 13:28:16]
  • 评测
  • 测评结果:0
  • 用时:61ms
  • 内存:7768kb
  • [2024-09-11 13:28:16]
  • 提交

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=1000000009;
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;
	
	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);
	
	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));
	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);
}
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);
	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: 3928kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

8

result:

wrong answer 1st lines differ - expected: '7', found: '8'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 57ms
memory: 7752kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 61ms
memory: 7748kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 61ms
memory: 7768kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Wrong Answer
time: 61ms
memory: 7756kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

10

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%