QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714652 | #9522. A Simple String Problem | PixelCat | AC ✓ | 922ms | 173636kb | C++17 | 5.1kb | 2024-11-06 01:41:31 | 2024-11-10 22:38:29 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-06 01:41:31]
- 提交
answer
#include <bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define eb emplace_back
const int MAXN = 200'000;
const int LGN = 21;
const int N = MAXN * 2 + 10;
const int U = 1;
const int D = 2;
struct Bruh {
int len, is_rev;
int sa[N], tmp[2][N], c[N], rk[N], lcp[N], min_lcp[LGN][N];
void buildSA(string s) {
int *x = tmp[0], *y = tmp[1], m = 256, n = s.length();
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
for(int i = 1; i < m; i++) c[i] += c[i - 1];
for(int i = n - 1; ~i; --i) sa[--c[x[i]]] = i;
for(int k = 1; k < n; k <<= 1) {
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[i]]++;
for(int i = 1; i < m; i++) c[i] += c[i - 1];
int p = 0;
for(int i = n - k; i < n; i++) y[p++] = i;
for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
y[sa[0]] = p = 0;
for(int i = 1; i < n; i++) {
int a = sa[i], b = sa[i - 1];
if(!(x[a] == x[b] && a + k < n && b + k < n && x[a + k] == x[b + k])) p++;
y[sa[i]] = p;
}
if(n == p + 1) break;
swap(x, y), m = p + 1;
}
}
void buildLCP(string s) {
int n = s.length(), val = 0;
for(int i = 0; i < n; i++) rk[sa[i]] = i;
for(int i = 0; i < n; i++) {
if(!rk[i]) lcp[rk[i]] = 0;
else {
if(val) val--;
int p = sa[rk[i] - 1];
while(val + i < n && val + p < n && s[val + i] == s[val + p]) val++;
lcp[rk[i]] = val;
}
}
for(int i = 1; i < n; i++) min_lcp[0][i] = lcp[i];
for(int j = 0; j < LGN - 1; j++) {
for(int i = 1; i < n; i++) {
min_lcp[j + 1][i] = min_lcp[j][i];
if(i + (1 << j) < n) min_lcp[j + 1][i] = min(min_lcp[j + 1][i], min_lcp[j][i + (1 << j)]);
}
}
}
void init(string &s, int _len, int _is_rev) {
buildSA(s);
buildLCP(s);
len = _len;
is_rev = _is_rev;
}
int mapid(int u, int i) {
if(i < 0 || i >= len) return -1;
if(is_rev) i = len - 1 - i;
if(u == D) i += len + 1;
return i;
}
int _match(int i, int j) {
if(i < 0 || j < 0) return 0;
assert(i != j);
i = rk[i]; j = rk[j];
if(i > j) swap(i, j);
int k = __lg(j - i);
return min(min_lcp[k][i + 1], min_lcp[k][j - (1 << k) + 1]);
}
int match(int u1, int i1, int u2, int i2) {
return _match(mapid(u1, i1), mapid(u2, i2));
}
} sa, as;
void findRep(int n, int l, int r, int &ans, int phase) {
if(l == r) return;
int m = (l + r - phase) / 2;
findRep(n, l, m, ans, phase);
findRep(n, m + 1, r, ans, phase);
for(int i = l; i <= m; i++) {
int k1, k2, k3;
auto sanitize = [&](int matched, int len, int lineno) {
if(len >= 8) {
cout << l << " " << i << "-" << m << " " << r << ": " << k1 << " " << k2 << " " << k3 << " at line " << lineno << "\n";
}
};
#ifndef NYA
#define verify(len) {if((len) >= (m - i + 1)) ans = max(ans, (m - i + 1) * 2);}
#else
#define verify(len) {if((len) >= (m - i + 1)) {ans = max(ans, (m - i + 1) * 2); sanitize(len, (m - i + 1) * 2, __LINE__);}}
#endif
k1 = sa.match(D, i, D, m + 1);
k2 = as.match(D, i - 1, D, m);
k3 = as.match(U, i - 1 - k2, D, m - k2);
verify(k1 + k2 + k3);
k1 = sa.match(U, i, D, m + 1);
k2 = as.match(U, i - 1, D, m);
k3 = sa.match(D, i + k1, D, m + 1 + k1);
verify(k1 + k2 + k3);
k1 = sa.match(U, i, D, m + 1);
k2 = as.match(U, i - 1, D, m);
k3 = as.match(U, i - 1 - k2, U, m - k2);
verify(k1 + k2 + k3);
k1 = sa.match(U, i, U, m + 1);
k2 = as.match(U, i - 1, U, m);
k3 = sa.match(U, i + k1, D, m + 1 + k1);
verify(k1 + k2 + k3);
}
}
void solve()
{
int n; cin >> n;
string up, down; cin >> up >> down;
up = up + "!";
down = "?" + down;
int ans = 0;
rep(phase, 2) {
string s;
s = up + "$" + down;
sa.init(s, n + 1, 0);
// cout << s << "\n";
reverse(up.begin(), up.end());
reverse(down.begin(), down.end());
s = up + "$" + down;
as.init(s, n + 1, 1);
// cout << s << "\n";
findRep(n + 1, 0, n, ans, phase);
swap(up, down);
}
cout << ans << "\n";
}
signed main()
{
MottoHayaku
int t;
// cin>>t;
t=1;
while(t--)
{
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 112204kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 112172kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 112200kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 112048kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 112168kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 112172kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 922ms
memory: 173412kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 865ms
memory: 173416kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 858ms
memory: 173412kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 695ms
memory: 173340kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 705ms
memory: 173408kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 809ms
memory: 173548kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 549ms
memory: 173636kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 112392kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 112104kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 3ms
memory: 112104kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 112180kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 112368kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 112176kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 112100kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 4ms
memory: 112048kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed