QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#679073 | #9522. A Simple String Problem | ucup-team4504# | AC ✓ | 542ms | 85760kb | C++14 | 3.3kb | 2024-10-26 16:48:09 | 2024-10-26 16:48:10 |
Judging History
你现在查看的是测评时间为 2024-10-26 16:48:10 的历史记录
- [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 16:48:09]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int N = 4e5 + 5;
int n;
char a[N], b[N];
struct SA{
int n, sa[N], rk[N], tot, t[N], y[N], _r[N];
int height[N];
char c[N];
int log2n, st[25][N];
void getsa(){
vector<pair<int, int>> vec;
for (int i = 1; i <= n; i++) vec.emplace_back(c[i], i);
sort(vec.begin(), vec.end());
for (int i = 1; i <= n; i++) sa[i] = vec[i - 1].second;
for (int i = 1; i <= n; i++) rk[sa[i]] = rk[sa[i - 1]] + (c[sa[i]] != c[sa[i - 1]]);
for (int step = 1; step <= n; step <<= 1){
tot = 0;
for (int i = n - step + 1; i <= n; i++) y[++tot] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > step)
y[++tot] = sa[i] - step;
memset(t, 0, sizeof(t));
for (int i = 1; i <= n; i++) t[rk[i]]++;
for (int i = 1; i <= n; i++) t[i] += t[i - 1];
for (int i = n; i >= 1; i--) sa[t[rk[y[i]]]--] = y[i];
memcpy(_r, rk, sizeof(_r));
for (int i = 1; i <= n; i++) rk[sa[i]] = rk[sa[i - 1]] + (_r[sa[i]] != _r[sa[i - 1]] || _r[sa[i] + step] != _r[sa[i - 1] + step]);
}
}
void getheight(){
int same = 0;
for (int i = 1; i <= n; i++){
if (rk[i] == 1){
same = 0;
continue;
}
if (same) same--;
int j = sa[rk[i] - 1];
while (i + same <= n && j + same <= n && c[i + same] == c[j + same]) same++;
height[rk[i]] = same;
}
}
void getst(){
log2n = log2(n);
for (int i = 2; i <= n; i++) st[0][i] = height[i];
for (int j = 1; j <= log2n; j++)
for (int i = 2; i + (1 << j) - 1 <= n; i++)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int lcp(int i, int j){
i = rk[i], j = rk[j];
if (i > j) swap(i, j);
i++;
int t = 31 ^ __builtin_clz(j - i + 1);
return min(st[t][i], st[t][j - (1 << t) + 1]);
}
void init(){
getsa();
getheight();
getst();
}
}sa1, sa2;
int lcppre(int a, int b, int p1, int p2){
p1 += a * n;
p2 += b * n;
return sa1.lcp(p1, p2);
}
int lcpsuf(int a, int b, int p1, int p2){
p1 = 2 * n - p1 + 1;
p2 = 2 * n - p2 + 1;
p1 -= a * n;
p2 -= b * n;
return sa2.lcp(p1, p2);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> (a + 1) >> (b + 2);
a[n + 1] = '?';
n++;
b[1] = '&';
sa1.n = sa2.n = n * 2;
for (int i = 1; i <= n * 2; i++){
sa1.c[i] = i <= n ? a[i] : b[i - n];
sa2.c[i] = i <= n ? b[n - i + 1] : a[n - (i - n) + 1];
}
sa1.init();
sa2.init();
for (int i = n; i >= 1; i--){
bool flg = 0;
for (int j = i; j <= n; j += i){
{
int len2 = lcpsuf(0, 0, j, j - i);
int len1 = lcppre(0, 0, j - i + 1, j + 1);
int len11 = lcppre(0, 1, j - i + 1 + len1, j + 1 + len1);
if (len2 + len1 + len11 >= i) flg = 1;
}
{
int len2 = lcpsuf(1, 1, j, j - i);
int len1 = lcppre(1, 1, j - i + 1, j + 1);
int len22 = lcpsuf(1, 0, j - len2, j - i - len2);
if (len2 + len22 + len1 >= i) flg = 1;
}
{
int len2 = lcpsuf(1, 0, j, j - i);
int len1 = lcppre(0, 1, j - i + 1, j + 1);
int len22 = lcpsuf(0, 0, j - len2, j - i - len2);
int len11 = lcppre(1, 1, j - i + 1 + len1, j + 1 + len1);
if (len2 + len1 + max(len22, len11) >= i) flg = 1;
}
}
if (flg){
cout << i * 2;
return 0;
}
}
cout << 0;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 34808kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 30640kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 6ms
memory: 32476kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 36448kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 30436kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 30308kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 343ms
memory: 85572kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 337ms
memory: 85760kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 350ms
memory: 83364kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 433ms
memory: 85592kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 239ms
memory: 84488kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 262ms
memory: 85596kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 542ms
memory: 83544kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 34344kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 3ms
memory: 39088kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 36656kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 6ms
memory: 34356kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 3ms
memory: 30608kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 26280kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 4ms
memory: 42532kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 4ms
memory: 44612kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed