QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#680973#9522. A Simple String Problemucup-team191#AC ✓464ms79400kbC++234.1kb2024-10-26 23:54:232024-10-26 23:54:24

Judging History

你现在查看的是测评时间为 2024-10-26 23:54:24 的历史记录

  • [2024-11-10 22:37:06]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:460ms
  • 内存:79452kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:38]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:418ms
  • 内存:79512kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:18:31]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:477ms
  • 内存:79468kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:30:43]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:716ms
  • 内存:79512kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-27 18:38:27]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:470ms
  • 内存:79520kb
  • [2024-10-27 18:36:42]
  • hack成功,自动添加数据
  • (/hack/1075)
  • [2024-10-26 23:54:24]
  • 评测
  • 测评结果:100
  • 用时:464ms
  • 内存:79400kb
  • [2024-10-26 23:54:23]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
#define sz(a) ((int)(a).size())
#define rep(i, a, b) for(int i = (a);(i) < (b);(i)++)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
const int LG = 19;


struct RMQ {
	vi lvl[LG];
	
	RMQ() {}
	RMQ(vi &v) {
		lvl[0] = v;
		lvl[0].erase(lvl[0].begin());
		int n = (int)v.size();
		for(int j = 1;j < LG;j++) {
			lvl[j].resize(n);
			for(int i = 0;i < n;i++) {
				lvl[j][i] = min(lvl[j - 1][i], lvl[j - 1][min(i + (1 << (j - 1)), n - 1)]);
			}
		}
	}
	
	int get_min(int i, int j) {
		int val = __lg(j - i + 1);
		//cout << i << " " << j << " " << val << " " << min(lvl[val][i], lvl[val][j - (1 << val) + 1]) <<  endl;
		return min(lvl[val][i], lvl[val][j - (1 << val) + 1]);
	}
};

struct SuffixArray {
	vi sa, lcp, inv;
	RMQ M;
	SuffixArray() {}
	SuffixArray(string &s, int lim=256) {
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
		inv.resize(n + 1);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] = 
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		rep(i, 1, n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
				s[i + k] == s[j + k]; k++);
		rep(i, 0, n) inv[sa[i]] = i;
		M = RMQ(lcp);
	}
	
	int get_lcp(int i, int j) {
		i = inv[i], j = inv[j];
		return M.get_min(min(i, j), max(i, j) - 1);
	}
	
};

int n;
string s1, s2;
SuffixArray Sa, Ra;

// i je fiksan, j mora biti gore
int fuzzy_lcp(int i, int j, SuffixArray &S = Sa) {
	if(i < 0 || i == n || i > 2 * n) return 0;
	if(j < 0 || j == n || j > 2 * n) return 0;
	assert(j < n);
	int x = S.get_lcp(i, j);
	int y = S.get_lcp(i + x, j + x + n);
	return x + y;
}

int fuzzy_lcs(int i, int j) {
	assert(j >= n);
	return fuzzy_lcp(2 * n - i, 2 * n - j, Ra);
}

bool check(int k) {
	for(int i = 0;i + k - 1 < n;i += k) {
		int lft = Ra.get_lcp(2 * n - i, 2 * n - ((n + 1) + (i + k - 1)));
		int rig = fuzzy_lcp((n + 1) + (i + k - 1), i);
		if(lft + rig >= k + 1 && s1[i] == s2[i + k - 1]) {
			//cout << lft << " " << rig << endl;
			//cout << i << endl;
			//cout << 1 << endl;
			return true;
		}
		
		lft = fuzzy_lcs(i, (n + 1) + (i + k - 1));
		rig = Sa.get_lcp((n + 1) + (i + k - 1), i);
		if(lft + rig >= k + 1 && s1[i] == s2[i + k - 1]) {
			//cout << lft << " " << rig << endl;
			//cout << i << endl;
			//cout << 1 << endl;
			return true;
		}
		
		
		lft = Sa.get_lcp(i, i + k);
		rig = Ra.get_lcp(2 * n - (i - 1), 2 * n - (i + k - 1));
		if(lft + rig >= k) {
			//cout << 2 << endl;
			return true;
		}
		
		lft = Sa.get_lcp((n + 1) + i, (n + 1) + i + k);
		rig = Ra.get_lcp(2 * n - (i - 1) - (n + 1), 2 * n - (i + k - 1) - (n + 1));
		if(lft + rig >= k) {
			//cout << lft << " " << rig << endl;
			//cout << i << " " << 3 << endl;
			return true;
		}
		
		lft = Ra.get_lcp(2 * n - (i - 1), 2 * n - (i + k - 1));
		rig = fuzzy_lcp(i, i + k);
		if(lft + rig >= k) {
			//cout << 4 << endl;
			return true;
		}
		lft = fuzzy_lcs((n + 1) + (i + k - 1), (n + 1) + (i - 1));
		rig = Sa.get_lcp((n + 1) + i, (n + 1) + i + k);
		if(lft + rig >= k) {
			//cout << lft << " " << rig << endl;
			//cout << i << " " << 5 << endl;
			return true;
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s1 >> s2;
	string S = s1 + "*" + s2;
	string RS = S;
	reverse(RS.begin(), RS.end());
	Sa = SuffixArray(S);
	Ra = SuffixArray(RS);
	int ans = n;
	//printf("%d\n", check(3));
	//return 0;
	while(ans > 0 && !check(ans)) ans--;
	cout << 2 * ans << endl;
}

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

詳細信息

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

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: 3544kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 255ms
memory: 79384kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 236ms
memory: 79376kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 254ms
memory: 79332kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 464ms
memory: 79304kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 199ms
memory: 79316kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 203ms
memory: 79400kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 354ms
memory: 79320kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed