QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684099 | #9522. A Simple String Problem | ucup-team918 | AC ✓ | 312ms | 46932kb | C++17 | 3.2kb | 2024-10-28 10:21:13 | 2024-11-10 22:37:16 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-28 15:17:17]
- hack成功,自动添加数据
- (/hack/1080)
- [2024-10-28 14:28:57]
- hack成功,自动添加数据
- (/hack/1079)
- [2024-10-28 10:21:13]
- 提交
answer
#include <bits/stdc++.h>
#define cerr cout << "in " << __LINE__ << "\t: "
using namespace std;
#define lg(x) (31 ^ __builtin_clz(x))
int n;
string s[2], t;
const int N = 400010;
int m = 128, old[N << 1], rk[N], sa[N], cnt[N], key[N], key2[N], h[N];
int st[20][N];
int LCP(int x, int y) {
x = rk[x], y = rk[y];
if (x > y) swap(x, y);
int len = lg(y - (x++));
return min(st[len][x], st[len][y - (1 << len) + 1]);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> s[0] >> s[1];
t = s[0] + '#' + s[1] + '*', n = n * 2 + 1;
for (int i = 1; i <= n; i++) cnt[rk[i] = t[i - 1]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
for (int w = 1;; w <<= 1) {
int p = 0;
for (int i = n; i > n - w; i--) key2[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > w) key2[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) cnt[key[i] = rk[key2[i]]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
memcpy(old, rk, sizeof(rk));
for (int i = n; i > 0; i--) sa[cnt[key[i]]--] = key2[i];
p = 0;
for (int i = 1; i <= n; i++) {
int x = sa[i], y = sa[i - 1];
rk[sa[i]] = p += old[x] != old[y] || old[x + w] != old[y + w];
}
if ((m = p) == n) break;
}
for (int i = 1, k = 0; i <= n; ++i) {
if (rk[i] == 1) continue;
if (k) --k;
while (t[i + k - 1] == t[sa[rk[i] - 1] + k - 1]) ++k;
h[rk[i]] = k;
}
for (int i = 1; i <= n; i++)
st[0][i] = h[i];
for (int i = 1; i < 20; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
n /= 2;
int res = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
for (int j = 1; j <= n; j += max(1, i - 1)) {
if (j + i > n) continue;
int tmp = LCP(j, j + i);
if (tmp == 0) continue;
if (tmp >= i) {res = i * 2; continue;}
int tmp2 = LCP(j + tmp, j + tmp + i + n);
if (tmp + tmp2 >= i) {res = i * 2; continue;}
int l = j - (i - tmp - tmp2);
if (l > 0 && LCP(l, l + i) >= i - tmp - tmp2) res = i * 2;
}
for (int j = 1; j <= n; j += max(1, i - 1)) {
if (j + i > n) continue;
int tmp = LCP(j + n + 1, j + i + n + 1);
if (tmp == 0) continue;
if (tmp >= i) {res = i * 2; continue;}
int l = j - (i - tmp);
if (l < 0) continue;
int tmp2 = LCP(l + 1, l + n + 1 + i);
if (tmp2 >= i - tmp) {res = i * 2; continue;}
if (l + tmp2 <= 0) continue;
if (LCP(l + 1 + tmp2 + n, l + 1 + tmp2 + n + i) >= i - tmp - tmp2) res = i * 2;
}
for (int j = 1; j <= n; j += max(1, i - 1)) {
if (j + i - 1 > n) continue;
int tmp = LCP(j, j + i + n);
if (tmp == 0) continue;
if (tmp >= i) {res = i * 2; continue;}
int tmp2 = LCP(j + tmp + n, j + i + tmp + n);
if (tmp2 >= i - tmp) {res = i * 2; continue;}
int l = j - (i - tmp - tmp2);
if (l > 0 && LCP(l, l + i + n) >= i - tmp - tmp2)
{res = i * 2; continue;}
l = j - (i - tmp);
if (l <= 0) continue;
tmp2 = LCP(l, l + i);
if (tmp2 >= i - tmp) {res = i * 2; continue;}
if (LCP(l + tmp2, l + tmp2 + i + n) >= i - tmp) res = i * 2;
}
}
cout << res << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 21980kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 4ms
memory: 21924kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 2ms
memory: 18116kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 22008kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 19972kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 21940kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 193ms
memory: 46156kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 187ms
memory: 45352kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 186ms
memory: 45380kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 206ms
memory: 45152kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 243ms
memory: 46160kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 312ms
memory: 46932kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 105ms
memory: 46612kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 24044kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 3ms
memory: 23984kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 24044kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 2ms
memory: 21928kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 2ms
memory: 19940kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 2ms
memory: 15860kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 3ms
memory: 26192kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 28092kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed