QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#680102 | #9522. A Simple String Problem | ucup-team296# | AC ✓ | 1002ms | 79288kb | C++20 | 5.5kb | 2024-10-26 19:49:59 | 2024-11-10 22:36:53 |
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-27 18:36:42]
- hack成功,自动添加数据
- (/hack/1075)
- [2024-10-26 19:49:59]
- 提交
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct sufmas {
void count_sort(vector<int> &p, vector<int> &c) {
int n = p.size();
vector<int> cnt(n);
for (auto x: c) {
cnt[x]++;
}
vector<int> p_new(n);
vector<int> pos(n);
pos[0] = 0;
for (int i = 1; i < n; i++) {
pos[i] = pos[i - 1] + cnt[i - 1];
}
for (auto x: p) {
int i = c[x];
p_new[pos[i]] = x;
pos[i]++;
}
p = p_new;
}
vector<int> p;
vector<int> c;
vector<int> lcp;
vector<vector<int>> st;
const int MAX = 20;
const char SPECIAL = 0;
string ss;
sufmas(string s) {
// ss = s;
// cout << s << "\n";
s += SPECIAL;
int n = s.size();
p.resize(n);
c.resize(n);
{
// k = 0
vector<pair<char, int>> a(n);
for (int i = 0; i < n; i++) a[i] = {s[i], i};
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) p[i] = a[i].second;
c[p[0]] = 0;
for (int i = 1; i < n; i++) {
if (a[i].first == a[i - 1].first && a[i].first != SPECIAL) {
c[p[i]] = c[p[i - 1]];
} else {
c[p[i]] = c[p[i - 1]] + 1;
}
}
}
int k = 0;
while ((1 << k) < n) {
// k -> k + 1
for (int i = 0; i < n; i++) {
p[i] = (p[i] - (1 << k) + n) % n;
}
count_sort(p, c);
vector<int> c_new(n);
c_new[p[0]] = 0;
for (int i = 1; i < n; i++) {
pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]};
pair<int, int> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
if (now == prev) {
c_new[p[i]] = c_new[p[i - 1]];
} else {
c_new[p[i]] = c_new[p[i - 1]] + 1;
}
}
c = c_new;
k++;
}
lcp.resize(n);
k = 0;
for (int i = 0; i < n - 1; i++) {
int pi = c[i];
if (pi > 0) {
int j = p[pi - 1];
// lcp[i] = lcp(s[i..], s[j..])
while (s[i + k] == s[j + k] && s[i + k] != SPECIAL) k++;
}
lcp[pi] = k;
k = max(k - 1, 0);
}
st.assign(MAX, vector<int>(n));
st[0] = lcp;
for (int k = 1; k < MAX; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
int get_lcp(int i, int j) {
if (i == p.size() || j == p.size()) return 0;
i = c[i];
j = c[j];
if (i > j) swap(i, j);
i++,j++;
int d = (j - i);
int k = 0;
while ((1 << (k + 1)) <= d) k++;
return min(st[k][i], st[k][j - (1 << k)]);
}
};
int n;
int lcp(int c1, int p1, int c2, int p2, sufmas &sm1) {
return sm1.get_lcp(c1 * n + p1, c2 * n + p2);
}
int rlcp(int c1, int p1, int c2, int p2, sufmas &sm2) {
return sm2.get_lcp(2 * n - 1 - c1 * n - p1, 2 * n - 1 - c2 * n - p2);
}
int res = 0;
void go(int l, int r, sufmas &sm1, sufmas &sm2) {
if (r - l < 2) return;
int m = (l + r) / 2;
go(l, m, sm1, sm2);
go(m, r, sm1, sm2);
for (int i = m + 1; i <= r; i++) {
int len = i - m;
if (len <= res) continue;
{
int x = rlcp(0, m - 1, 0, i - 1, sm2);
x = min(x, len);
x = min(x, m - l);
int y = lcp(0, m, 0, i, sm1);
y = min(y, len);
y = min(y, r - i);
int z = 0;
if (x + y < len) {
z = lcp(0, m + y, 1, i + y, sm1);
}
if (x + y + z >= len) {
res = max(res, len);
}
}
{
int x = rlcp(0, m - 1, 1, i - 1, sm2);
x = min(x, len);
x = min(x, m - l);
int y = lcp(0, m, 1, i, sm1);
y = min(y, len);
y = min(y, r - i);
int z = 0;
if (x + y < len) {
z = max(
lcp(1, m + y, 1, i + y, sm1),
rlcp(0, m - 1 - x, 0, i - 1 - x, sm2));
}
if (x + y + z >= len) {
res = max(res, len);
}
}
}
for (int i = l; i < m; i++) {
int len = m - i;
if (len <= res) continue;
{
int x = rlcp(0, i - 1, 0, m - 1, sm2);
x = min(x, len);
x = min(x, m - l);
int y = lcp(0, i, 0, m, sm1);
int z = 0;
if (x + y < len) {
z = lcp(0, i + y, 1, m + y, sm1);
}
if (x + y + z >= len) {
res = max(res, len);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
string s1, s2;
cin >> n >> s1 >> s2;
s1 = s1 + '$';
s2 = '$' + s2;
n++;
string r = s1 + s2;
sufmas sm1(r);
reverse(r.begin(), r.end());
sufmas sm2(r);
go(0, n, sm1, sm2);
go(0, n, sm2, sm1);
cout << res * 2 << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1002ms
memory: 78996kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 699ms
memory: 79232kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 971ms
memory: 78928kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 766ms
memory: 78996kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 267ms
memory: 79288kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 513ms
memory: 78956kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 974ms
memory: 79168kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3580kb
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: 3560kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed