QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#689540#9522. A Simple String Problem123456zmyAC ✓1342ms10472kbC++143.2kb2024-10-30 17:38:392024-11-10 22:37:48

Judging History

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

  • [2024-11-10 22:37:48]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1342ms
  • 内存:10472kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:21]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1327ms
  • 内存:10508kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-30 17:38:46]
  • 评测
  • 测评结果:100
  • 用时:1366ms
  • 内存:11532kb
  • [2024-10-30 17:38:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
const int mod = (int)1e16 + gen(), base = gen() % 100 + 100;

vector<int> b{ 1 };
struct Hash {
	vector<int> h{ 0 };
	void append(auto& s) {
		for (auto x : s)
			h.push_back((h.back() * base + x) % mod);
		for (int i = b.size(); i <= s.size(); i++)
			b.push_back((b.back() * base) % mod);
	}
	int query(int l, int r) {
		if (l > r || l < 1 || r >= h.size())
			return gen();
		int x = h[r] - (__int128)h[l - 1] * b[r - l + 1] % mod;
		return x + (x < 0) * mod;
	}
	Hash() {}
	Hash(auto& s) {
		append(s);
	}
};

#define endl '\n'
using ll = long long;

void solve()
{
	int n;
	cin >> n;

	string s[2], t[2];
	cin >> t[0] >> t[1];
	s[0] = " " + t[0] + " ";
	s[1] = "  " + t[1];

	Hash h[2];
	h[0] = Hash(t[0]);
	string ht = " " + t[1];
	h[1] = Hash(ht);

	auto check = [&](auto p) {
		auto [x, y] = p;
		if (!x && (!y || y > n))
			return 0;
		if (x && (!y || y > n + 1))
			return 0;
		return 1;
	};
	auto lcp = [&](auto a, auto b) {
		auto [x1, y1] = a;
		auto [x2, y2] = b;
		if (!check(a) || !check(b) || s[x1][y1] != s[x2][y2])
			return 0ll;
		int l = 1, r = n;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (h[x1].query(y1, y1 + mid - 1) == h[x2].query(y2, y2 + mid - 1))
				l = mid;
			else
				r = mid - 1;
		}
		return l;
	};
	auto lcs = [&](auto a, auto b) {
		auto [x1, y1] = a;
		auto [x2, y2] = b;
		if (!check(a) || !check(b) || s[x1][y1] != s[x2][y2])
			return 0ll;
		int l = 1, r = n;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (h[x1].query(y1 - mid + 1, y1) == h[x2].query(y2 - mid + 1, y2))
				l = mid;
			else
				r = mid - 1;
		}
		return l;
	};

	int ans1 = 0, ans2 = 0, ans3 = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j += i) {
			int l = j, r = l + i - 1;
			// case1 : 
			if (r <= n) {

				int len1 = lcp(make_pair(0, l), make_pair(0, r + 1));
				int len2 = lcp(make_pair(0, l + len1), make_pair(1, r + len1 + 1));
				int len3 = lcs(make_pair(0, l - 1), make_pair(0, r));
				if (len1 + len2 + len3 >= i) {
					ans1 = max(ans1, 2 * i);
					break;
				}
			}
			// case2 :
			if (r <= n + 1) {
				int len1 = lcp(make_pair(1, l), make_pair(1, r + 1));
				int len2 = lcs(make_pair(1, l - 1), make_pair(1, r));
				int len3 = lcs(make_pair(0, l - len2 - 1), make_pair(1, r - len2));

				//debug(i, j, l - len2 - 1, r - len2, len1, len2, len3, endl);
				if (len1 + len2 + len3 >= i) {
					ans2 = max(ans2, 2 * i);
					break;
				}
			}
			// case3:
			if (r <= n) {
				int len1 = lcp(make_pair(0, l), make_pair(1, r + 1));
				int len2 = lcs(make_pair(0, l - 1), make_pair(1, r));
				//int len3 = lcs(make_pair(1, l + len1 + 1), make_pair(1, r + len1 + 1));

				//debug(i, len1, len2, len3, endl);
				//debug(l, r, endl);

				if (len1 + len2 >= i) {
					ans3 = max(ans3, 2 * i);
					break;
				}
			}
		}
	}

	//debug(ans1, ans2, ans3, endl);
	cout << max({ ans1, ans2, ans3 }) << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
}

/*

5
aabba
baaba


*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 146ms
memory: 10464kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 146ms
memory: 10312kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 143ms
memory: 10468kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 717ms
memory: 10320kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1244ms
memory: 10468kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 1342ms
memory: 10472kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 145ms
memory: 10256kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed