QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#747437#9522. A Simple String ProblemcomplexorAC ✓406ms83052kbC++204.5kb2024-11-14 17:10:062024-11-14 17:10:11

Judging History

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

  • [2024-11-14 17:10:11]
  • 评测
  • 测评结果:AC
  • 用时:406ms
  • 内存:83052kb
  • [2024-11-14 17:10:06]
  • 提交

answer

#include <bits/stdc++.h>
typedef unsigned long long ULL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair
#define clr(f, n) memset(f, 0, (n) << 2)
#define cpy(f, g, n) memcpy(f, g, (n) << 2)
#define reve(f, n) std::reverse(f, (f) + (n))
int read()
{
	int s = 0; int f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c ^ 48), c = getchar();
	return f ? s : -s;
} 
const int MAXN = 200005, inf = 0x3f3f3f3f, MAXV = 600005;
template<typename T> T& Fmax(T& x, T y){ return x = x < y ? y : x; };
template<typename T> T& Fmin(T& x, T y){ return x = x < y ? x : y; };
int n, lg[MAXN << 1];
char s[2][MAXN];
struct A_string_data_structure
{
	int sa[MAXN << 1], rnk[MAXN << 1], ht[MAXN << 1], n, nn, st[20][MAXN << 1];
	bool rev;
	char s[MAXN << 1];
	void suffix_sort()
	{
		static int cnt[MAXN << 1], id[MAXN << 1], oldrk[MAXN << 1];
		clr(cnt, 200);
		for (int i = 1; i <= nn; i++) cnt[s[i]]++;
		for (int i = 1; i < 200; i++) cnt[i] += cnt[i - 1];
		for (int i = 1; i <= nn; i++) sa[cnt[s[i]]--] = i;
		rnk[sa[1]] = 1;
		for (int i = 2; i <= nn; i++)
			rnk[sa[i]] = rnk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
		int V = rnk[sa[nn]];
		auto cmp = [=](int i, int j, int w)->bool{
			if (oldrk[i] != oldrk[j]) return false;
			return (i > nn - w && j > nn - w) || (i <= nn - w && j <= nn - w && oldrk[i + w] == oldrk[j + w]);
		};
//		for (int i = 1; i <= nn; i++)
//			printf("%d: %d %d\n", i, sa[i], rnk[i]);
		for (int w = 1; V < nn; w <<= 1, V = rnk[sa[nn]])
		{
			int cur = 0;
			for (int i = nn; i > nn - w; i--) id[++cur] = i;
			for (int i = 1; i <= nn; i++)
				if (sa[i] > w) id[++cur] = sa[i] - w;
			
			clr(cnt + 1, V);
			for (int i = 1; i <= nn; i++) cnt[rnk[id[i]]]++;
			for (int i = 1; i <= V; i++) cnt[i] += cnt[i - 1];
			for (int i = nn; i; i--) sa[cnt[rnk[id[i]]]--] = id[i];
			
			cpy(oldrk + 1, rnk + 1, nn), rnk[sa[1]] = 1;
			for (int i = 2; i <= nn; i++)
				rnk[sa[i]] = rnk[sa[i - 1]] + !cmp(sa[i], sa[i - 1], w);
		}
	}
	void gen_height()
	{
		for (int i = 1, j = 0; i <= nn; i++)
		{
			if (j) j--;
			if (rnk[i] == nn) continue;
			int ii = sa[rnk[i] + 1];
			while (i + j <= nn && ii + j <= nn && s[i + j] == s[ii + j]) ++j;
			ht[rnk[i]] = j;
		}
	}
	#define pw(x) (1 << (x))
	void gen_sparse_table()
	{
		cpy(st[0] + 1, ht + 1, nn);
		for (int i = 1; i <= lg[nn]; i++)
			for (int j = 1; j + pw(i) - 1 <= nn; j++)
				st[i][j] = std::min(st[i - 1][j], st[i - 1][j + pw(i - 1)]);
	}
	int query(int l, int r)
	{
		l = rnk[l], r = rnk[r];
		if (l == r) return -1;
		if (l > r) std::swap(l, r);
		int len = lg[r - l];
		return std::min(st[len][l], st[len][r - pw(len)]);
	}
	#undef pw
	void init(int _n, char str[2][MAXN], bool _r)
	{
		n = _n, nn = n << 1;
		memcpy(s + 1, str[0] + 1, n);
		memcpy(s + n + 1, str[1] + 1, n);
		if (rev = _r) reve(s + 1, n), reve(s + n + 1, n);
		suffix_sort(), gen_height(), gen_sparse_table();
//		printf("%s\n", s + 1);
//		for (int i = 1; i <= nn; i++)
//			printf("%d: %d %d %d\n", i, sa[i], rnk[i], ht[i]);
	}
	int q_same(int o, int l, int r)
	{ 
		if (rev) l = n + 1 - l, r = n + 1 - r; 
		if (l > n || r > n) return 0;
		return query(l + o * n, r + o * n); 
	}
	int q_dif(int l, int r)
	{
		if (rev) l = n + 1 - l, r = n + 1 - r; 
		if (l > n || r > n) return 0;
		return query(l, r + n); 
	}
} pre, suf;
int main()
{
	n = read() + 1;
	scanf("%s", s[0] + 1), s[0][n] = '$';
	scanf("%s", s[1] + 2), s[1][1] = '@';
	for (int i = 2; i <= n * 2; i++) lg[i] = lg[i >> 1] + 1;
	pre.init(n, s, 1);
//	printf("%s\n%s\n", s[0] + 1, s[1] + 1);
//	printf("%d\n", pre.q_dif(3, 6));
	suf.init(n, s, 0);
	for (int len = n / 2; len; len--)
		for (int i = 1, ii = len + 1; ii <= n; ii += len, i += len)
		{
			int lenl = pre.q_same(0, i - 1, ii - 1), lenr = suf.q_same(0, i, ii); 
			if (lenl + lenr + suf.q_dif(i + lenr, ii + lenr) >= len) return printf("%d\n", len * 2), 0;
			
			lenl = pre.q_same(1, i - 1, ii - 1), lenr = suf.q_same(1, i, ii); 
			if (lenl + lenr + pre.q_dif(i - lenl - 1, ii - lenl - 1) >= len) return printf("%d\n", len * 2), 0;
			
			lenl = pre.q_dif(i - 1, ii - 1), lenr = suf.q_dif(i, ii); 
			if (lenl + lenr + pre.q_same(0, i - lenl - 1, ii - lenl - 1) >= len) return printf("%d\n", len * 2), 0;
			if (lenl + lenr + suf.q_same(1, i + lenr, ii + lenr) >= len) return printf("%d\n", len * 2), 0;
		}
	printf("0\n");
	return 0;
}
/*
5
abcab
acabc

6
*/

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 3ms
memory: 30428kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 240ms
memory: 80952kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 226ms
memory: 83052kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 248ms
memory: 81052kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 406ms
memory: 80736kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 197ms
memory: 82896kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 204ms
memory: 82804kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 314ms
memory: 82968kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 3ms
memory: 36568kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed