QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710935 | #9522. A Simple String Problem | ucup-team3519 | AC ✓ | 1970ms | 14832kb | C++17 | 4.0kb | 2024-11-04 23:17:37 | 2024-11-10 22:38:16 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-04 23:17:37]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define fi first
#define se second
#define V vector
#define pb push_back
typedef long long LL;
const LL mod = 444445555566666677;
const LL base = 2333;
const int N = 1e6 + 20;
typedef uint64_t ull;
struct H {
ull x; H(ull x=0) : x(x) {}
H operator+(H o) { return x + o.x + (x + o.x < x); }
H operator-(H o) { return *this + ~o.x; }
H operator*(H o) { auto m = (__uint128_t)x * o.x;
return H((ull)m) + (ull)(m >> 64); }
ull get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator<(H o) const { return get() < o.get(); }
};
H pbs[N];
H mul(H a, H b) {
return a * b;
}
int deal(int n, string a, string b, int prev_ans) {
int ans = prev_ans;
V<H> prea(n + 1);
V<H> preb(n + 1);
for(int i = 1; i <= n; i++) {
prea[i] = mul(prea[i - 1], base) + a[i];
preb[i] = mul(preb[i - 1], base) + b[i];
}
auto hasha = [&](int l, int r) -> H {
assert(r >= l);
return prea[r] - mul(prea[l - 1], pbs[r - l + 1]);
};
auto hashb = [&](int l, int r) -> H {
assert(r >= l);
return preb[r] - mul(preb[l - 1], pbs[r - l + 1]);
};
auto is_1 = [&](int l, int r, int k) -> bool {
assert(r >= l);
if(r + k > n) return 0;
return hasha(l, r) == hasha(l + k, r + k);
};
auto is_2 = [&](int l, int r, int k) -> bool {
assert(r >= l);
if(r + k - 1 > n) return 0;
return hasha(l, r) == hashb(l + k - 1, r + k - 1);
};
for(int k = n; k >= 1; k--) {
// if(ans >= k * 2) break;
for(int j = k; j <= n; j += k) {
if(is_1(j, j, k)) {
int l = 0, r = j;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_1(mid, j, k)) r = mid;
else l = mid;
}
int L1 = r;
l = j, r = n + 1;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_1(j, mid, k)) l = mid;
else r = mid;
}
int R1 = l;
//1 -> 2?
l = R1, r = n + 1;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_2(R1 + 1, mid, k)) l = mid;
else r = mid;
}
int R2 = l;
if(R2 - L1 + 1 >= k) {
ans = max(ans, 2 * k);
}
}
if(is_2(j, j, k)) {
int l = 0, r = j;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_2(mid, j, k)) r = mid;
else l = mid;
}
int L2 = r;
l = j, r = n + 1;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_2(j, mid, k)) l = mid;
else r = mid;
}
int R2 = l;
//1 -> 2?
l = 0, r = L2;
while(l != r - 1) {
int mid = l + r >> 1;
if(is_1(mid, L2 - 1, k)) r = mid;
else l = mid;
}
int L1 = r;
if(R2 - L1 + 1 >= k) {
ans = max(ans, 2 * k);
}
}
}
}
return ans;
}
void solve() {
int n; cin >> n;
string a, b; cin >> a >> b;
a = " " + a, b = " " + b;
int ans = deal(n, a, b, 0);
reverse(a.begin() + 1, a.end());
reverse(b.begin() + 1, b.end());
ans = max(ans, deal(n, b, a, ans));
cout << ans << endl;
}
int main() {
pbs[0] = 1;
for(int i = 1; i < N; i++) pbs[i] = mul(base, pbs[i - 1]);
ios::sync_with_stdio(0), cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 11384kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 4ms
memory: 11336kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 4ms
memory: 11316kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 11340kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 4ms
memory: 11436kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 4ms
memory: 11328kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 227ms
memory: 14760kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 219ms
memory: 14680kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 231ms
memory: 14664kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1138ms
memory: 14756kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1947ms
memory: 14740kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 1970ms
memory: 14832kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 229ms
memory: 14680kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 4ms
memory: 11388kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 4ms
memory: 11556kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 11436kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 11324kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 4ms
memory: 11304kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 4ms
memory: 11384kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 4ms
memory: 11332kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 4ms
memory: 11396kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed