QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744317 | #7780. Dark LaTeX vs. Light LaTeX | Suhy | TL | 604ms | 16404kb | C++17 | 2.5kb | 2024-11-13 21:30:36 | 2024-11-13 21:30:39 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int maxn = 10004;
const int b1 = 31;
const int b2 = 37;
int n, m;
int s[maxn], t[maxn];
ull ps1[maxn], ps2[maxn], pt1[maxn], pt2[maxn];
unordered_map <ull, int> mp1;
ull pwb1[maxn], pwb2[maxn];
ll ans;
int f[maxn], cnt[maxn];
//babaa
void wok(int dlt)
{
for(int i = 2; i < n; i ++)
{
int j = f[i - 1];
while(j > 0 && (s[j + 1 + dlt] != s[i + dlt] || (i + dlt > n && (i + dlt - j <= n || j + dlt >= n))))
j = f[j];
if(s[j + 1 + dlt] == s[i + dlt])
j ++;
f[i] = j;
cnt[i] = 0;
if(j != 0) cnt[i] ++;
cnt[i] += cnt[j];
int l = i + dlt - n + 1;
int r = dlt;
if(l > 1)
{
//cout<<l<<' '<<r<<' '<<cnt[i]<<' '<<i<<' '<<f[i]<<' '<<s[i + dlt]<<' '<<s[1 + dlt]<<' ';
// for(int j = l; j <= r; j ++)
// putchar(s[j] + 'a' - 1);
// cout<<endl;
ans += cnt[i] * mp1[ps1[r] - ps1[l - 1] * pwb1[r - l + 1]];
//cout<<ps1[r] - ps1[l - 1] * pwb1[r - l + 1]<<endl;
}
}
}
void work()
{
mp1.clear();
for(int i = 1; i <= m; i ++)
{
for(int j = 1; j <= i; j ++)
{
mp1[pt1[i] - pt1[j - 1] * pwb1[(i - j + 1)]] ++;
}
}
for(int i = 1; i <= n; i ++)
s[i + n] = s[i];
for(int i = 1; i < n; i ++)
{
wok(i);
}
}
signed main()
{
char c = getchar();
while('a' <= c && c <= 'z')
s[++ n] = c - 'a' + 1, c = getchar();
while(!('a' <= c && c <= 'z'))
c = getchar();
while('a' <= c && c <= 'z')
t[++ m] = c - 'a' + 1, c = getchar();
for(int i = 1; i <= n; i ++)
{
ps1[i] = ps1[i - 1] * b1 + s[i];
}
for(int i = 1; i <= m; i ++)
{
pt1[i] = pt1[i - 1] * b1 + t[i];
}
pwb1[0] = pwb2[0] = 1;
for(int i = 1; i <= max(n, m); i ++)
{
pwb1[i] = 1ll * pwb1[i - 1] * b1;
}
work();
//cout<<"-----"<<endl;
swap(n, m);
for(int i = 1; i <= max(n, m); i ++)
{
swap(s[i], t[i]);
swap(ps1[i], pt1[i]);
}
work();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= i; j ++)
{
ull hsh1 = ps1[i] - ps1[j - 1] * pwb1[(i - j + 1)];
ans += mp1[hsh1];
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 604ms
memory: 4236kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 136ms
memory: 16136kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 132ms
memory: 16404kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: -100
Time Limit Exceeded
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...