QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558008#8668. 回文路径zero-range0 28ms9848kbC++201.6kb2024-09-11 13:27:552024-09-11 13:27:56

Judging History

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

  • [2024-09-11 13:27:56]
  • 评测
  • 测评结果:0
  • 用时:28ms
  • 内存:9848kb
  • [2024-09-11 13:27:55]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#define M 200005
using namespace std;
typedef unsigned long long ull;
constexpr ull bs=1000;
ull Ha[M],Hb[M],Pa[M],Pb[M],pw[M];
inline ull queh(ull *H,int l,int r){return H[r]-H[l-1]*pw[r-l+1];}
inline ull quep(ull *P,int l,int r){return P[l]-P[r+1]*pw[r-l+1];}
int n,res;
char a[M],b[M];
int main(){
	pw[0]=1;
	for(int i=1;i<M;++i) pw[i]=pw[i-1]*bs;
	scanf("%d%s%s",&n,a+1,b+1);
	for(int i=n;i;--i) a[i*2]=a[i],a[i*2+1]='#';
	a[1]='#';
	for(int i=n;i;--i) b[i*2+1]=b[i],b[i*2+2]='#';
	b[1]='@',b[2]='#',a[n=n*2+2]='.';
	for(int i=1;i<=n;++i) Ha[i]=Ha[i-1]*bs+a[i];
	for(int i=n;i;--i) Pa[i]=Pa[i+1]*bs+a[i];
	for(int i=1;i<=n;++i) Hb[i]=Hb[i-1]*bs+b[i];
	for(int i=n;i;--i) Pb[i]=Pb[i+1]*bs+b[i];
	for(int i=1;i<=n;++i){
		int l=1,r=min(i-1,n-i),mid,ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-mid,i-1)==quep(Pa,i+1,i+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		int t=ans;
		res=max(res,t*2+1);
		l=1,r=min(i-t-1,n-i+1-t),ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-t-mid,i-t-1)==quep(Pb,i+t,i+t+mid-1)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		res=max(res,(t+ans)*2+1);
	}
	for(int i=1;i<=n;++i){
		int l=1,r=min(i-1,n-i),mid,ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Hb,i-mid,i-1)==quep(Pb,i+1,i+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		int t=ans;
		res=max(res,t*2+1);
		l=1,r=min(i-t,n-i-t),ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-t-mid+1,i-t)==quep(Pb,i+t+1,i+t+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		res=max(res,(t+ans)*2+1);
	}
	printf("%d",res/2);
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

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

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

831

result:

wrong answer 1st lines differ - expected: '28', found: '831'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 23ms
memory: 9840kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

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

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 28ms
memory: 9788kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 24ms
memory: 9848kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 0
Wrong Answer
time: 18ms
memory: 9780kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

100000

result:

wrong answer 1st lines differ - expected: '99999', found: '100000'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%