QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308251 | #6567. Repetitive String Invention | Mizara# | AC ✓ | 570ms | 8844kb | C++17 | 3.9kb | 2024-01-19 19:50:26 | 2024-01-19 19:50:27 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <math.h>
#include <utility>
const int OO = 0;
const int md = 998244353;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<iii> viii;
const int N = 808;
int r[N][N], l[N][N];
int n;
string s;
int PS[N], kmp[N];
void do_kmp(int i, int j) {
int len = j - i + 1;
kmp[0] = 0;
for (int ind = 1; ind < len; ind++) {
kmp[ind] = kmp[ind - 1] + 1; // candidate
while (kmp[ind] > 1 && s[i + kmp[ind] - 1] != s[i + ind])
kmp[ind] = kmp[kmp[ind] - 2] + 1;
if (s[i + kmp[ind] - 1] != s[i + ind])
kmp[ind] = 0;
}
for (int i = 0; i <= len; i++) PS[i] = 0;
int suflen = kmp[len - 1];
while (suflen > 0) {
if (2 * suflen < len) {
PS[(len - 2 * suflen + 1) / 2] += 2;
}
suflen = kmp[suflen - 1];
}
PS[(len + 1) / 2]++;
for (int i = 1; i <= len; i++) PS[i] += PS[i - 1];
}
int calc_odd(int st, int en) {
int c = (st + en) / 2;
int cl, cr;
int ans = 0;
for (int i = 0; i < st; i++) {
cr = min(r[i][c], st - i);
cl = l[i][c];
cl = min(cl, en - st + 1);
ans += PS[min(cl, cr)];
}
for (int i = en + 1; i < n; i++) {
cr = r[i][c];
cl = min(l[i][c], i - en);
cl = min(cl, en - st + 1);
ans += PS[min(cl, cr)];
}
return ans;
}
int calc_even(int st, int en) {
int c = (st + en) / 2;
int cl, cr;
int ans = 0;
for (int i = 0; i < st - 1; i++) {
cr = min(r[i + 1][c + 1], st - i - 1);
cl = l[i][c];
cl = min(cl, en - st + 1);
ans += PS[min(cl, cr)];
}
for (int i = en + 1; i < n - 1; i++) {
cr = r[i + 1][c + 1];
cl = min(l[i][c], i - en);
cl = min(cl, en - st + 1);
ans += PS[min(cl, cr)];
}
return ans;
}
int calc(int st, int en) {
do_kmp(st, en);
if ((en - st + 1) % 2 == 1) return calc_odd(st, en);
return calc_even(st, en);
}
int brute_calc(int st, int en) {
int ans = 0;
for (int x = 0; x < n; x++) for (int y = x; y < n; y++) {
if (!(y < st || en < x)) continue;
if (y - x > en - st) continue;
string cur;
if (y < st) cur = s.substr(x, y - x + 1) + s.substr(st, en - st + 1);
else cur = s.substr(st, en - st + 1) + s.substr(x, y - x + 1);
if (cur.size() & 1) continue;
int l = cur.size() / 2;
if (cur.substr(0, l) == cur.substr(l, l)) {
if (y - x == en - st) ans++;
else ans += 2;
}
}
return ans;
}
ll brute() {
ll ans = 0;
for (int i = 0; i < n; i++) for (int j = i; j < n; j++)
for (int x = j + 1; x < n; x++) for (int y = x; y < n; y++) {
string cur = s.substr(i, j - i + 1) + s.substr(x, y - x + 1);
if (cur.size() & 1) continue;
int l = cur.size() / 2;
if (cur.substr(0, l) == cur.substr(l, l))
ans++;
}
return ans;
}
void solve() {
cin >> s;
n = s.size();
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
if (i >= 1)
r[i][j] = max(0, r[i - 1][j - 1] - 1);
while (i + r[i][j] < n && j + r[i][j] < n && s[i + r[i][j]] == s[j + r[i][j]]) r[i][j]++;
r[j][i] = r[i][j];
}
// l
for (int i = n - 1; i >= 0; i--) for (int j = i - 1; j >= 0; j--) {
if (i < n - 1)
l[i][j] = max(0, l[i + 1][j + 1] - 1);
while (i - l[i][j] >= 0 && j - l[i][j] >= 0 && s[i - l[i][j]] == s[j - l[i][j]]) l[i][j]++;
l[j][i] = l[i][j];
}
ll ans = 0;
for (int st = 0; st < n; st++) for (int en = st; en < n; en++) {
int tmp = calc(st, en);
if (OO) {
cout << "calc(" << st << ", " << en << "):\t" << tmp << endl;
//if (OO) cout << "brute:\t\t" << brute_calc(st, en) << endl;
//cout << endl;
}
ans += tmp;
}
cout << ans / 2 << endl;
if (OO) {
cout << "brute: " << brute() << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tests = 1;
//cin >> tests;
while (tests--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
aaaa
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
axabxbcxcdxd
output:
22
result:
ok single line: '22'
Test #3:
score: 0
Accepted
time: 69ms
memory: 6316kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
536006700
result:
ok single line: '536006700'
Test #4:
score: 0
Accepted
time: 57ms
memory: 6044kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
136016600
result:
ok single line: '136016600'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
a
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
ab
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
aa
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 44ms
memory: 7012kb
input:
bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...
output:
209015
result:
ok single line: '209015'
Test #9:
score: 0
Accepted
time: 36ms
memory: 5992kb
input:
fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...
output:
5696
result:
ok single line: '5696'
Test #10:
score: 0
Accepted
time: 39ms
memory: 7240kb
input:
ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...
output:
18249
result:
ok single line: '18249'
Test #11:
score: 0
Accepted
time: 39ms
memory: 6184kb
input:
lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...
output:
207835
result:
ok single line: '207835'
Test #12:
score: 0
Accepted
time: 37ms
memory: 7284kb
input:
lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...
output:
3442
result:
ok single line: '3442'
Test #13:
score: 0
Accepted
time: 44ms
memory: 7108kb
input:
yjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjy...
output:
103111
result:
ok single line: '103111'
Test #14:
score: 0
Accepted
time: 49ms
memory: 6104kb
input:
lhllhlhlhllhlhllhhlhhhhllhhlhhhhllhhlhhhhllhllhhllhhlhhhhllhllhhhhhllhhlhhhhhlhllhlhhlhllhlhhhhllhllhhhllhhlhhhhhhlhllhlhllhhlhhhhhhlhllhlhhllhllllhllhhhlhllhlhhhllhhlhhhhhhllhhlhhhhlhllhlhllhllhhhhllhllllhllllhllllhlllhllhlhllhhlhhhhhhhllhlllhllhlhllhhlhhhhllhllllhlllhllhlhllhllhhhhhhhllhhlhhhhllhh...
output:
298186
result:
ok single line: '298186'
Test #15:
score: 0
Accepted
time: 48ms
memory: 6124kb
input:
blbllblbblbllblbblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblbblbllblblblbblllblbblllblbblllblbbllblbllblblblbblllblbblllblbbllblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbblllblbblllblbbllblbllblblblbblllblbblllblbblll...
output:
510790
result:
ok single line: '510790'
Test #16:
score: 0
Accepted
time: 44ms
memory: 6316kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
584698
result:
ok single line: '584698'
Test #17:
score: 0
Accepted
time: 570ms
memory: 8776kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
8554693400
result:
ok single line: '8554693400'
Test #18:
score: 0
Accepted
time: 484ms
memory: 8600kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
2154733200
result:
ok single line: '2154733200'
Test #19:
score: 0
Accepted
time: 397ms
memory: 8632kb
input:
abbbabbaaababbaabaaababaababbaabbbbbaaababbbbababbaabababaabbbaaabbababbababbabbbaabbabaaabaaabbbabbabbabaaaabbabbbababaabaabbaaaabbbbbbbababaabaababaaaaaabbbbbbbaaabaabaababbabaabababbbbabbabbaabbbaaababbbbabababababaabbbbbbbbbabbbbababaaabbbaababbbbaabbbbaabbaababbaaaababbabbabbabbabbaaaaaabbbbaab...
output:
930632
result:
ok single line: '930632'
Test #20:
score: 0
Accepted
time: 358ms
memory: 8844kb
input:
acbaabcbabcccccbbaaacaaacbacaabccbbccabbbaaacacbaccbaaaaaacbbcbabacaabaaabcbccbbccbaaabacacccacccbabcbbcaaabbaacaaabaabcaaccbacacbcbcacbbbbaacbbcccbbccabcacaaabcbbbbacbcbcaabbbccaabbcbacbcaccabbbcccccbcbbbabcabcacbccccacabccbccbccaaccbbbbbccbabbbcaabbaacaccacbcbaabbbbabbccbcacacbbcacbbccbacbbbcacccc...
output:
304687
result:
ok single line: '304687'
Test #21:
score: 0
Accepted
time: 329ms
memory: 8636kb
input:
gvqghqqtyruttomyqtjlimqxhhoiboxzggiduzwyaagmtvvogqwcfsgvnvzncgmhtpjtmnqekqyhzyvvnfofasxkcvrhlydmpfulmeugpayixcixaijfmkvhhbgikpyjlmvzrzbkhmtymjfkqzwafvimebzixveouiuwlkljnilpzdvrcygbtdsimysonrpolsunmdeqgatgudbkuihzgkqgucfczlhytrshtdhlvekmhnjllqfpkjwwujiifikmfvcpijojmnkjivvmbuweauqofpxnazdyisttwabrofjz...
output:
13605
result:
ok single line: '13605'
Test #22:
score: 0
Accepted
time: 388ms
memory: 8784kb
input:
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmn...
output:
14989915
result:
ok single line: '14989915'
Test #23:
score: 0
Accepted
time: 393ms
memory: 8524kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
2798983
result:
ok single line: '2798983'