QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110901 | #6567. Repetitive String Invention | He_Ren# | AC ✓ | 169ms | 6328kb | C++17 | 895b | 2023-06-04 16:14:14 | 2023-06-04 16:14:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 800 + 5;
int n;
char s[MAXN];
pair<ll,ll> getres(void)
{
ll res1 = 0, res2 = 0;
static int cnt[MAXN][MAXN];
memset(cnt, 0, sizeof(cnt));
for(int i=1; i<=n; ++i)
{
for(int j=i+1; j<=n; ++j)
{
for(int k=1; i+k<=j-1 && j+k-1<=n; ++k)
{
if(s[i+k-1] != s[j+k-1]) break;
res1 += cnt[i+k][j-1];
}
}
for(int j=i+1; j<=n; ++j)
{
for(int k=1; i-k+1>=1 && j-k+1>i; ++k)
{
if(s[i-k+1] != s[j-k+1]) break;
++cnt[j-k+1][j];
++res2;
}
}
}
return {res1, res2};
}
int main(void)
{
scanf("%s",s+1);
n = strlen(s+1);
ll ans = 0;
auto t = getres();
ans += t.first + t.second;
reverse(s+1, s+n+1);
t = getres();
ans += t.first;
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 6040kb
input:
aaaa
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 6100kb
input:
axabxbcxcdxd
output:
22
result:
ok single line: '22'
Test #3:
score: 0
Accepted
time: 25ms
memory: 6292kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
536006700
result:
ok single line: '536006700'
Test #4:
score: 0
Accepted
time: 16ms
memory: 6104kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
136016600
result:
ok single line: '136016600'
Test #5:
score: 0
Accepted
time: 4ms
memory: 6104kb
input:
a
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 6160kb
input:
ab
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 4ms
memory: 6144kb
input:
aa
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 4ms
memory: 6188kb
input:
bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...
output:
209015
result:
ok single line: '209015'
Test #9:
score: 0
Accepted
time: 2ms
memory: 6280kb
input:
fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...
output:
5696
result:
ok single line: '5696'
Test #10:
score: 0
Accepted
time: 2ms
memory: 6100kb
input:
ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...
output:
18249
result:
ok single line: '18249'
Test #11:
score: 0
Accepted
time: 6ms
memory: 6184kb
input:
lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...
output:
207835
result:
ok single line: '207835'
Test #12:
score: 0
Accepted
time: 3ms
memory: 6036kb
input:
lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...
output:
3442
result:
ok single line: '3442'
Test #13:
score: 0
Accepted
time: 2ms
memory: 6108kb
input:
yjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjy...
output:
103111
result:
ok single line: '103111'
Test #14:
score: 0
Accepted
time: 5ms
memory: 6100kb
input:
lhllhlhlhllhlhllhhlhhhhllhhlhhhhllhhlhhhhllhllhhllhhlhhhhllhllhhhhhllhhlhhhhhlhllhlhhlhllhlhhhhllhllhhhllhhlhhhhhhlhllhlhllhhlhhhhhhlhllhlhhllhllllhllhhhlhllhlhhhllhhlhhhhhhllhhlhhhhlhllhlhllhllhhhhllhllllhllllhllllhlllhllhlhllhhlhhhhhhhllhlllhllhlhllhhlhhhhllhllllhlllhllhlhllhllhhhhhhhllhhlhhhhllhh...
output:
298186
result:
ok single line: '298186'
Test #15:
score: 0
Accepted
time: 6ms
memory: 6044kb
input:
blbllblbblbllblbblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblbblbllblblblbblllblbblllblbblllblbbllblbllblblblbblllblbblllblbbllblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbblllblbblllblbbllblbllblblblbblllblbblllblbblll...
output:
510790
result:
ok single line: '510790'
Test #16:
score: 0
Accepted
time: 4ms
memory: 6188kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
584698
result:
ok single line: '584698'
Test #17:
score: 0
Accepted
time: 169ms
memory: 6124kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
8554693400
result:
ok single line: '8554693400'
Test #18:
score: 0
Accepted
time: 93ms
memory: 6188kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
2154733200
result:
ok single line: '2154733200'
Test #19:
score: 0
Accepted
time: 9ms
memory: 6044kb
input:
abbbabbaaababbaabaaababaababbaabbbbbaaababbbbababbaabababaabbbaaabbababbababbabbbaabbabaaabaaabbbabbabbabaaaabbabbbababaabaabbaaaabbbbbbbababaabaababaaaaaabbbbbbbaaabaabaababbabaabababbbbabbabbaabbbaaababbbbabababababaabbbbbbbbbabbbbababaaabbbaababbbbaabbbbaabbaababbaaaababbabbabbabbabbaaaaaabbbbaab...
output:
930632
result:
ok single line: '930632'
Test #20:
score: 0
Accepted
time: 12ms
memory: 6096kb
input:
acbaabcbabcccccbbaaacaaacbacaabccbbccabbbaaacacbaccbaaaaaacbbcbabacaabaaabcbccbbccbaaabacacccacccbabcbbcaaabbaacaaabaabcaaccbacacbcbcacbbbbaacbbcccbbccabcacaaabcbbbbacbcbcaabbbccaabbcbacbcaccabbbcccccbcbbbabcabcacbccccacabccbccbccaaccbbbbbccbabbbcaabbaacaccacbcbaabbbbabbccbcacacbbcacbbccbacbbbcacccc...
output:
304687
result:
ok single line: '304687'
Test #21:
score: 0
Accepted
time: 6ms
memory: 6328kb
input:
gvqghqqtyruttomyqtjlimqxhhoiboxzggiduzwyaagmtvvogqwcfsgvnvzncgmhtpjtmnqekqyhzyvvnfofasxkcvrhlydmpfulmeugpayixcixaijfmkvhhbgikpyjlmvzrzbkhmtymjfkqzwafvimebzixveouiuwlkljnilpzdvrcygbtdsimysonrpolsunmdeqgatgudbkuihzgkqgucfczlhytrshtdhlvekmhnjllqfpkjwwujiifikmfvcpijojmnkjivvmbuweauqofpxnazdyisttwabrofjz...
output:
13605
result:
ok single line: '13605'
Test #22:
score: 0
Accepted
time: 13ms
memory: 6044kb
input:
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmn...
output:
14989915
result:
ok single line: '14989915'
Test #23:
score: 0
Accepted
time: 10ms
memory: 6120kb
input:
aqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaqaaqaqqaaqqaqaaqaqqaqaaqqaaqaqqaaqqaqaaqqaaq...
output:
2798983
result:
ok single line: '2798983'