QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706712#6567. Repetitive String Inventionucup-team902#WA 528ms7080kbC++171.0kb2024-11-03 13:05:172024-11-03 13:05:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 13:05:17]
  • 评测
  • 测评结果:WA
  • 用时:528ms
  • 内存:7080kb
  • [2024-11-03 13:05:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=800;
const int g=27,mod=998244353;
int n;
char s[N+5];
int hv[N+5][N+5];
unordered_map<int,int> cnt;
ll ans;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n&&j-i+1<=n/2;j++)
            hv[i][j]=(1ll*hv[i][j-1]*g+s[j]-'a'+1)%mod;
    for(int d=1;d<=n/2;d++){
        cnt.clear();
        for(int j=n;j>=d;j--){
            for(int i=j-d+1;i&&j-i+1<2*d;i--)
                if(hv[i][j-d]==hv[i+d][j])
                    ans+=cnt[hv[j-d+1][i+d-1]];
            for(int i=j;i<=n&&i-j+1<=d;i++)
                cnt[hv[j][i]]++;
        }
        cnt.clear();
        for(int i=1;i<=n;i++){
            for(int j=i+d;j<=n&&j-i+1<2*d;j++){
                if(hv[i][j-d]==hv[i+d][j])
                    ans+=cnt[hv[j-d+1][i+d-1]];
            }
            for(int j=i;j&&i-j+1<=d;j--)
                cnt[hv[j][i]]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

aaaa

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

axabxbcxcdxd

output:

22

result:

ok single line: '22'

Test #3:

score: 0
Accepted
time: 97ms
memory: 5388kb

input:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

536006700

result:

ok single line: '536006700'

Test #4:

score: 0
Accepted
time: 77ms
memory: 5020kb

input:

abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

136016600

result:

ok single line: '136016600'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

a

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4128kb

input:

ab

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

aa

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 428ms
memory: 6912kb

input:

bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...

output:

209015

result:

ok single line: '209015'

Test #9:

score: 0
Accepted
time: 479ms
memory: 6820kb

input:

fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...

output:

5696

result:

ok single line: '5696'

Test #10:

score: 0
Accepted
time: 521ms
memory: 7040kb

input:

ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...

output:

18249

result:

ok single line: '18249'

Test #11:

score: 0
Accepted
time: 433ms
memory: 6892kb

input:

lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...

output:

207835

result:

ok single line: '207835'

Test #12:

score: 0
Accepted
time: 528ms
memory: 7048kb

input:

lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...

output:

3442

result:

ok single line: '3442'

Test #13:

score: 0
Accepted
time: 411ms
memory: 7080kb

input:

yjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjjjyjxjyjyyxjyjyjyyxxyyxxxjjxxxyyyjjjyxjyxjxjyjxjyyyjjxxxjxxjxjyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjyxxxxxjjxyxxyjjxxjyyjjjyyyxjyjxjxyjjxyyxjxyjjyxyyjxyyjxjxjxjyxyxxjxjjy...

output:

103111

result:

ok single line: '103111'

Test #14:

score: 0
Accepted
time: 472ms
memory: 7080kb

input:

lhllhlhlhllhlhllhhlhhhhllhhlhhhhllhhlhhhhllhllhhllhhlhhhhllhllhhhhhllhhlhhhhhlhllhlhhlhllhlhhhhllhllhhhllhhlhhhhhhlhllhlhllhhlhhhhhhlhllhlhhllhllllhllhhhlhllhlhhhllhhlhhhhhhllhhlhhhhlhllhlhllhllhhhhllhllllhllllhllllhlllhllhlhllhhlhhhhhhhllhlllhllhlhllhhlhhhhllhllllhlllhllhlhllhllhhhhhhhllhhlhhhhllhh...

output:

298186

result:

ok single line: '298186'

Test #15:

score: -100
Wrong Answer
time: 375ms
memory: 6844kb

input:

blbllblbblbllblbblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblblblbbllblbllblblblbbllblbllblbblbllblbblbllblblblbblllblbblllblbblllblbbllblbllblblblbblllblbblllblbbllblbllblblblbblllblbbllblbllblbblbllblbblbllblblblbblllblbblllblbbllblbllblblblbblllblbblllblbblll...

output:

510820

result:

wrong answer 1st lines differ - expected: '510790', found: '510820'