QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#850168#8668. 回文路径LittleAcbg100 ✓33ms9228kbC++143.1kb2025-01-09 21:05:512025-01-09 21:05:52

Judging History

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

  • [2025-01-09 21:05:52]
  • 评测
  • 测评结果:100
  • 用时:33ms
  • 内存:9228kb
  • [2025-01-09 21:05:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 2e5+9;
const int B = 131;
int n,ans;
char s1[N],s2[N];
ll h1[N],h2[N],rh1[N],rh2[N],p[N];
ll H1(int l, int r) {return h1[r] - h1[l - 1] * p[r - l + 1];}
ll H2(int l, int r) {return h2[r] - h2[l - 1] * p[r - l + 1];}
ll RH1(int l, int r) {return rh1[l] - rh1[r + 1] * p[r - l + 1];}
ll RH2(int l, int r) {return rh2[l] - rh2[r + 1] * p[r - l + 1];}
int main()
{
	scanf("%d %s %s", &n, s1 + 1, s2 + 1);
	p[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		h1[i] = h1[i - 1] * B + s1[i];
		h2[i] = h2[i - 1] * B + s2[i];
		p[i] = p[i - 1] * B;
	}
	for (int i = n; i >= 1; --i)
	{
		rh1[i] = rh1[i + 1] * B + s1[i];
		rh2[i] = rh2[i + 1] * B + s2[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		// s1 格子 
		int l = 1,r = min(i - 1, n - i),res = 0;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H1(i - mid, i - 1) == RH1(i + 1, i + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		int pos1 = i - res - 1,pos2 = i + res;
		l = 0,r = min(pos1 - 1, n - pos2),res = -1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H1(pos1 - mid, pos1) == RH2(pos2, pos2 + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		ans = max(ans, pos2 + res - pos1 + res + 2);
		
		// s2 格子
		l = 1,r = min(i - 1, n - i),res = 0;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H2(i - mid, i - 1) == RH2(i + 1, i + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		pos1 = i - res,pos2 = i + res + 1;
		l = 0,r = min(pos1 - 1, n - pos2),res = -1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H1(pos1 - mid, pos1) == RH2(pos2, pos2 + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		ans = max(ans, pos2 + res - pos1 + res + 2);
		
		// s1 s2 连接
		l = 0,r = min(i - 1, n - i),res = -1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H1(i - mid, i) == RH2(i, i + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		ans = max(ans, 2 * res + 2);
		
		if (i == n) continue;
		
		// s1 i~i+1 连接
		l = 0,r = min(i, n - i),res = -1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H1(i - mid, i) == RH1(i + 1, i + 1 + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		if (res != -1)
		{
			pos1 = i - res - 1,pos2 = i + 1 + res;
			l = 0,r = min(pos1 - 1, n - pos2),res = -1;
			while (l <= r)
			{
				int mid = (l + r) >> 1;
				if (H1(pos1 - mid, pos1) == RH2(pos2, pos2 + mid)) res = mid,l = mid + 1;
				else r = mid - 1;
			}
			ans = max(ans, pos2 + res - pos1 + res + 2);
		}
		
		// s2 i~i+1 连接
		l = 0,r = min(i, n - i),res = -1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (H2(i - mid, i) == RH2(i + 1, i + 1 + mid)) res = mid,l = mid + 1;
			else r = mid - 1;
		}
		if (res != -1)
		{
			pos1 = i - res,pos2 = i + 2 + res;
			l = 0,r = min(pos1 - 1, n - pos2),res = -1;
			while (l <= r)
			{
				int mid = (l + r) >> 1;
				if (H1(pos1 - mid, pos1) == RH2(pos2, pos2 + mid)) res = mid,l = mid + 1;
				else r = mid - 1;
			}
			ans = max(ans, pos2 + res - pos1 + res + 2);
		}
	}
	printf("%d\n", 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: 3952kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

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

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

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

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

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

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

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

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

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

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

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

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

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

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

36

result:

ok single line: '36'

Test #9:

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

input:

1000
aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...

output:

50

result:

ok single line: '50'

Test #10:

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

input:

1000
aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...

output:

20

result:

ok single line: '20'

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 22ms
memory: 9012kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 18ms
memory: 9016kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 22ms
memory: 8784kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

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

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 20
Accepted
time: 16ms
memory: 9188kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok single line: '99999'

Subtask #3:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #16:

score: 50
Accepted
time: 14ms
memory: 9156kb

input:

100000
vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...

output:

10

result:

ok single line: '10'

Test #17:

score: 50
Accepted
time: 18ms
memory: 8032kb

input:

100000
fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...

output:

9

result:

ok single line: '9'

Test #18:

score: 50
Accepted
time: 26ms
memory: 9100kb

input:

100000
baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...

output:

40

result:

ok single line: '40'

Test #19:

score: 50
Accepted
time: 22ms
memory: 9228kb

input:

100000
babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...

output:

43

result:

ok single line: '43'

Test #20:

score: 50
Accepted
time: 32ms
memory: 9124kb

input:

100000
aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...

output:

75

result:

ok single line: '75'

Test #21:

score: 50
Accepted
time: 28ms
memory: 8032kb

input:

100000
aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...

output:

58

result:

ok single line: '58'

Test #22:

score: 50
Accepted
time: 33ms
memory: 9140kb

input:

100000
abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...

output:

67

result:

ok single line: '67'

Test #23:

score: 50
Accepted
time: 29ms
memory: 8076kb

input:

100000
bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...

output:

55

result:

ok single line: '55'

Test #24:

score: 50
Accepted
time: 23ms
memory: 7884kb

input:

100000
cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...

output:

25

result:

ok single line: '25'

Test #25:

score: 50
Accepted
time: 20ms
memory: 8076kb

input:

100000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...

output:

96421

result:

ok single line: '96421'

Test #26:

score: 50
Accepted
time: 0ms
memory: 3892kb

input:

5
pkusc
pkukp

output:

6

result:

ok single line: '6'