QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558264#8668. 回文路径syp110 7ms18732kbC++141.2kb2024-09-11 15:13:282024-09-11 15:13:29

Judging History

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

  • [2024-09-11 15:13:29]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:18732kb
  • [2024-09-11 15:13:28]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=1e6+10;
const int B=13;
int n,res,pl[N];
ull pw[N],hsa[N],hsb[N];
char a[N],b[N];
void solve(char *a,char *b)
{
	pw[0]=1;
	hsa[0]=a[0];
	for(int i=1;i<=n;i++)
	{
		pw[i]=pw[i-1]*B;
		pl[i]=0;
	}
	for(int i=1;i<=n+1;i++)
	{
		hsa[i]=hsa[i-1]*B+a[i];
	}
	for(int i=n+1;i>=0;i--)
	{
		hsb[i]=hsb[i+1]*B+b[i];
	}
	for(int i=1,md=0,r=0;i<=n;i++)
	{
		if(i<=r)
		{
			pl[i]=min(pl[2*md-i],r-i+1);
		}
		while(a[i-pl[i]]==a[i+pl[i]])
		{
			pl[i]++;
		}
		if(i+pl[i]>r)
		{
			r=i+pl[i]-1;
			md=i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int p=max(res,pl[i]);
		for(;p<=i;p++)
		{
			ull x=hsa[i-pl[i]]-hsa[i-p-1]*pw[p-pl[i]+1];
			ull y=hsb[i+pl[i]-2]-hsb[i+p-1]*pw[p-pl[i]+1];
			if(x!=y)
			{
				break;
			}
		}
		res=max(res,p);
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	a[0]=b[0]='@';
	for(int i=1;i<=n;i++)
	{
		cin>>a[2*i];
		a[2*i-1]='#';
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[2*i];
		b[2*i-1]='#';
	}
	n<<=1;
	a[n+1]=b[n+1]='#';
	solve(a,b);
	reverse(a+2,a+n+1);
	reverse(b+2,a+n+1);
	solve(b,a);
	cout<<res-1<<flush;
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Accepted
time: 2ms
memory: 10772kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 11940kb

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

40

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 7ms
memory: 17152kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 0ms
memory: 18732kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 0
Wrong Answer
time: 4ms
memory: 18708kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

10

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%