QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558270#8668. 回文路径ccccccyd0 19ms10220kbC++142.1kb2024-09-11 15:15:342024-09-11 15:15:35

Judging History

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

  • [2024-09-11 15:15:35]
  • 评测
  • 测评结果:0
  • 用时:19ms
  • 内存:10220kb
  • [2024-09-11 15:15:34]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ph push_back
#define mk make_pair
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(int i(r),i##end(l);i>=i##end;--i)
using namespace std;
const int N=1e5+20;
int n,d[N<<1]; char a[N<<1]; vector<pair<int,int> > qry;
void manache(char str[]){
	int tn=n<<1|1;
	rep(i,1,tn) a[i]=(i&1)?'*':str[i>>1];
	int x=0;
	rep(i,1,tn){
		if(x+d[x]>i) d[i]=min(x+d[x]-i,d[x-(i-x)]);
		while(i-d[i]-1>0&&a[i-d[i]-1]==a[i+d[i]+1]) d[i]++;
		if(i+d[i]>x+d[x]) x=i;
		if(d[i]) qry.ph(mk((i-d[i])/2+1,(i+d[i])/2));
	}
}
const ll base0=1737,mod0=1e9+9,base1=2333,mod1=998244353;
int ans; char s[N],t[N]; ll ss0[N],st0[N],g0[N]={1},ss1[N],st1[N],g1[N]={1}; 
int solve(const int l,const int r){
	int lf=1,rg=min(l-1,n-r+1),m,k=0;
	while(lf<=rg){
		m=(lf+rg)>>1;
		if(((ss0[l-1]-ss0[l-1-m]*g0[m])-(st0[r]-st0[r+m]*g0[m]))%mod0==0
			&&((ss1[l-1]-ss1[l-1-m]*g1[m])-(st1[r]-st1[r+m]*g1[m]))%mod1==0) 
			k=m,lf=m+1;
		else rg=m-1;
	}
//	printf("%d %d  %d %d  %d\n",l,r,lf,rg,k);
	return r-l+1+k*2;
}
signed main(){
// 	freopen("1.in","r",stdin);
// 	freopen("1.out","w",stdout);
	scanf("%d%s%s",&n,s+1,t+1);
	rep(i,1,n) g0[i]=g0[i-1]*base0%mod0;
	rep(i,1,n) g1[i]=g1[i-1]*base1%mod1;
	
	rep(i,1,n) ss0[i]=(ss0[i-1]*base0+s[i]-'a')%mod0;
	per(i,n,1) st0[i]=(st0[i+1]*base0+t[i]-'a')%mod0;
	rep(i,1,n) ss1[i]=(ss1[i-1]*base1+s[i]-'a')%mod1;
	per(i,n,1) st1[i]=(st1[i+1]*base1+t[i]-'a')%mod1;
	manache(s);
	for(auto x:qry)	ans=max(ans,solve(x.first,x.second));//,printf("%d %d  %d\n",x.first,x.second,ans);
	rep(i,1,n) ans=max(ans,solve(i+1,i));
	cerr<<ans<<'\n';
	
//	reverse(s+1,s+n+1),reverse(t+1,t+n+1),swap(s,t);
	rep(i,1,n) ss0[i]=(ss0[i-1]*base0+s[i]-'a')%mod0;
	per(i,n,1) st0[i]=(st0[i+1]*base0+t[i]-'a')%mod0;
	rep(i,1,n) ss1[i]=(ss1[i-1]*base1+s[i]-'a')%mod1;
	per(i,n,1) st1[i]=(st1[i+1]*base1+t[i]-'a')%mod1;
	qry.clear(),manache(s);
	for(auto x:qry)	ans=max(ans,solve(x.first,x.second));//,printf("%d %d  %d\n",x.first,x.second,ans);
	rep(i,1,n) ans=max(ans,solve(i+1,i));
	cout<<ans;
	return 0;
}//g++ -g P4324.cpp -o my -std=c++14 -Wextra

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

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

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

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

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

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: 19ms
memory: 10048kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 19ms
memory: 10100kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Wrong Answer
time: 19ms
memory: 10220kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

9

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%