QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#689540 | #9522. A Simple String Problem | 123456zmy | AC ✓ | 1342ms | 10472kb | C++14 | 3.2kb | 2024-10-30 17:38:39 | 2024-11-10 22:37:48 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-30 17:38:39]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
const int mod = (int)1e16 + gen(), base = gen() % 100 + 100;
vector<int> b{ 1 };
struct Hash {
vector<int> h{ 0 };
void append(auto& s) {
for (auto x : s)
h.push_back((h.back() * base + x) % mod);
for (int i = b.size(); i <= s.size(); i++)
b.push_back((b.back() * base) % mod);
}
int query(int l, int r) {
if (l > r || l < 1 || r >= h.size())
return gen();
int x = h[r] - (__int128)h[l - 1] * b[r - l + 1] % mod;
return x + (x < 0) * mod;
}
Hash() {}
Hash(auto& s) {
append(s);
}
};
#define endl '\n'
using ll = long long;
void solve()
{
int n;
cin >> n;
string s[2], t[2];
cin >> t[0] >> t[1];
s[0] = " " + t[0] + " ";
s[1] = " " + t[1];
Hash h[2];
h[0] = Hash(t[0]);
string ht = " " + t[1];
h[1] = Hash(ht);
auto check = [&](auto p) {
auto [x, y] = p;
if (!x && (!y || y > n))
return 0;
if (x && (!y || y > n + 1))
return 0;
return 1;
};
auto lcp = [&](auto a, auto b) {
auto [x1, y1] = a;
auto [x2, y2] = b;
if (!check(a) || !check(b) || s[x1][y1] != s[x2][y2])
return 0ll;
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (h[x1].query(y1, y1 + mid - 1) == h[x2].query(y2, y2 + mid - 1))
l = mid;
else
r = mid - 1;
}
return l;
};
auto lcs = [&](auto a, auto b) {
auto [x1, y1] = a;
auto [x2, y2] = b;
if (!check(a) || !check(b) || s[x1][y1] != s[x2][y2])
return 0ll;
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (h[x1].query(y1 - mid + 1, y1) == h[x2].query(y2 - mid + 1, y2))
l = mid;
else
r = mid - 1;
}
return l;
};
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
int l = j, r = l + i - 1;
// case1 :
if (r <= n) {
int len1 = lcp(make_pair(0, l), make_pair(0, r + 1));
int len2 = lcp(make_pair(0, l + len1), make_pair(1, r + len1 + 1));
int len3 = lcs(make_pair(0, l - 1), make_pair(0, r));
if (len1 + len2 + len3 >= i) {
ans1 = max(ans1, 2 * i);
break;
}
}
// case2 :
if (r <= n + 1) {
int len1 = lcp(make_pair(1, l), make_pair(1, r + 1));
int len2 = lcs(make_pair(1, l - 1), make_pair(1, r));
int len3 = lcs(make_pair(0, l - len2 - 1), make_pair(1, r - len2));
//debug(i, j, l - len2 - 1, r - len2, len1, len2, len3, endl);
if (len1 + len2 + len3 >= i) {
ans2 = max(ans2, 2 * i);
break;
}
}
// case3:
if (r <= n) {
int len1 = lcp(make_pair(0, l), make_pair(1, r + 1));
int len2 = lcs(make_pair(0, l - 1), make_pair(1, r));
//int len3 = lcs(make_pair(1, l + len1 + 1), make_pair(1, r + len1 + 1));
//debug(i, len1, len2, len3, endl);
//debug(l, r, endl);
if (len1 + len2 >= i) {
ans3 = max(ans3, 2 * i);
break;
}
}
}
}
//debug(ans1, ans2, ans3, endl);
cout << max({ ans1, ans2, ans3 }) << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
}
/*
5
aabba
baaba
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 3636kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 146ms
memory: 10464kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 146ms
memory: 10312kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 143ms
memory: 10468kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 717ms
memory: 10320kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1244ms
memory: 10468kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 1342ms
memory: 10472kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 145ms
memory: 10256kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3872kb
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: 3612kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed