QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817271#6218. 扭动的回文串SGColin100 ✓144ms8360kbC++202.6kb2024-12-16 21:18:152024-12-16 21:18:15

Judging History

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

  • [2024-12-16 21:18:15]
  • 评测
  • 测评结果:100
  • 用时:144ms
  • 内存:8360kb
  • [2024-12-16 21:18:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

const int base = 31;
const int mod1 = 1000000007;
const int mod2 = 1000000009;

vector<pii> pw;

inline void init(int n) {
	int pw1 = 1, pw2 = 1;
	rep(i, 1, n) {
		pw.eb(pw1, pw2);
		pw1 = 1ll * pw1 * base % mod1;
		pw2 = 1ll * pw2 * base % mod2;
	}
}

struct HASH {
	vector<pii> h;
	HASH (string &str) {
		int h1 = 0, h2 = 0;
		for (auto c : str) {
			int x = c - 'A' + 1;
			h1 = (1ll * h1 * base + x) % mod1;
			h2 = (1ll * h2 * base + x) % mod2;
			h.eb(h1, h2);

		}
	} 
	inline pii getv(int l, int r) {
		auto [h1, h2] = h[r];
		if (l) {
			auto [hl1, hl2] = h[l - 1];
			auto [pw1, pw2] = pw[r - l + 1];
			h1 = ((h1 - 1ll * hl1 * pw1) % mod1 + mod1) % mod1;
			h2 = ((h2 - 1ll * hl2 * pw2) % mod2 + mod2) % mod2;
		}
		return {h1, h2};
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n; init(n);
	string a, b; cin >> a >> b;
	HASH A(a), B(b);
	reverse(all(a));
	reverse(all(b));
	HASH RA(a), RB(b);

	int ans = 0;

	auto LCP = [&](HASH &x, HASH &y, int posx, int posy) {
		int L = 0, R = min(n - posx, n - posy);
		while (L < R) {
			int mid = (L + R + 1) / 2;
			x.getv(posx, posx + mid - 1) == y.getv(posy, posy + mid - 1) ? L = mid : R = mid - 1;
		}
		return L;
	};

	rep(i, 0, n - 1) { // centered at a character i
		// center in A
		int L = 1, R = min(n - i, i + 1);
		while (L < R) {
			int mid = (L + R + 1) / 2;
			A.getv(i, i + mid - 1) == RA.getv(n - 1 - i, n - 2 + mid - i) ? L = mid : R = mid - 1;
		}
		ans = max(ans, L * 2 - 1 + LCP(RA, B, n - 1 - i + L, i + L - 1) * 2);
		// center in B
		L = 1, R = min(n - i, i + 1);
		while (L < R) {
			int mid = (L + R + 1) / 2;
			B.getv(i, i + mid - 1) == RB.getv(n - 1 - i, n - 2 + mid - i) ? L = mid : R = mid - 1;
		}
		ans = max(ans, L * 2 - 1 + LCP(RA, B, n - 2 - i + L, i + L) * 2);
	}	

	rep(i, 1, n) { // centered at a gap [i - 1, i]
		// center in A
		int L = 0, R = min(n - i, i);
		while (L < R) {
			int mid = (L + R + 1) / 2;
			A.getv(i, i + mid - 1) == RA.getv(n - i, n  - 1 + mid - i) ? L = mid : R = mid - 1;
		}
		ans = max(ans, L * 2 + LCP(RA, B, n - i + L, i + L - 1) * 2);
		// center in B
		L = 0, R = min(n - i, i);
		while (L < R) {
			int mid = (L + R + 1) / 2;
			B.getv(i, i + mid - 1) == RB.getv(n - i, n  - 1 + mid - i) ? L = mid : R = mid - 1;
		}
		ans = max(ans, L * 2 + LCP(RA, B, n - 1 - i + L, i + L) * 2);
	}

	printf("%d\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3748kb

input:

30
AABABAAAAABBBAAAAAABBAABAABABA
AAAAAAABABBAAAAAABABAAAABAAAAB

output:

23

result:

ok single line: '23'

Test #2:

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

input:

200
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAAB
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAABBAAAAAAAABAAAAAAAAABAAAAAAAAAAAAAAAA...

output:

75

result:

ok single line: '75'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3872kb

input:

200
AABAAAAAAAAAAAAAAAAAAAAABAAAAABAAABAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAAAAAABAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAABAAAAAAAAABBAAAAABAAAAAAAAAAAAAABAAAAABAAAAABBAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

117

result:

ok single line: '117'

Test #4:

score: 10
Accepted
time: 2ms
memory: 3860kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAA...

output:

429

result:

ok single line: '429'

Test #5:

score: 10
Accepted
time: 0ms
memory: 3932kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAA...

output:

660

result:

ok single line: '660'

Test #6:

score: 10
Accepted
time: 144ms
memory: 8360kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

10486

result:

ok single line: '10486'

Test #7:

score: 10
Accepted
time: 141ms
memory: 8128kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

16715

result:

ok single line: '16715'

Test #8:

score: 10
Accepted
time: 131ms
memory: 8128kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

50035

result:

ok single line: '50035'

Test #9:

score: 10
Accepted
time: 133ms
memory: 8220kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

20929

result:

ok single line: '20929'

Test #10:

score: 10
Accepted
time: 135ms
memory: 8196kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

40448

result:

ok single line: '40448'