QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #771541 | #7780. Dark LaTeX vs. Light LaTeX | Rubyonly | AC ✓ | 1399ms | 302908kb | C++23 | 3.7kb | 2024-11-22 14:02:34 | 2024-11-25 21:21:43 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e3 + 50, INF = 0x7f7f7f7f;
const ull base = 233;
inline int read() {
int x = 0, w = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int n, m;
char a[maxn], b[maxn], c[maxn << 1];
int fail[maxn << 1], lcp[maxn][maxn];
ll ans, cnt[maxn << 1], sum[maxn][maxn];
int main() {
scanf("%s%s", a + 1, b + 1), n = strlen(a + 1), m = strlen(b + 1);
for (int i = n; i >= 1; i --)
for (int j = n; j >= 1; j --)
if (a[i] == a[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
else lcp[i][j] = 0;
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
for (int i = 1; i <= n; i ++) {
int k = 0; memset(c, 0, sizeof c);
for (int j = i; j <= n; j ++) c[++ k] = a[j];
c[++ k] = '#';
for (int j = 1; j <= m; j ++) c[++ k] = b[j];
for (int j = 1; j <= k; j ++) fail[j] = 0;
for (int j = 2, t = 0; j <= k; j ++) {
while (t && c[t + 1] != c[j]) t = fail[t];
if (c[t + 1] == c[j]) fail[j] = ++ t;
}
for (int j = 1; j <= k; j ++) cnt[j] = 1;
for (int j = k; j >= 1; j --) cnt[fail[j]] += cnt[j];
for (int j = 1; j <= n - i + 1; j ++) sum[n - i - j + 2][n - i + 1] += cnt[j];
for (int j = 1; j <= n - i + 1; j ++) fail[j] = 0;
for (int j = 2, t = 0; j <= n - i + 1; j ++) {
while (t && c[t + 1] != c[j]) t = fail[t];
if (c[t + 1] == c[j]) fail[j] = ++ t;
}
for (int j = 1; j <= n - i + 1; j ++) cnt[j] = 1;
for (int j = n - i + 1; j >= 1; j --) cnt[fail[j]] += cnt[j];
for (int j = 1; j <= n - i + 1; j ++) sum[n - i - j + 2][n - i + 1] -= cnt[j];
}
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
ans += sum[i][j];
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
sum[j][i] += sum[j - 1][i];
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
ans += sum[i + min(lcp[i][j], j - i - 1)][j - 1] - sum[i][j - 1];
memset(lcp, 0, sizeof lcp);
memset(sum, 0, sizeof sum);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
for (int i = m; i >= 1; i --)
for (int j = m; j >= 1; j --)
if (b[i] == b[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
else lcp[i][j] = 0;
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
for (int i = 1; i <= m; i ++) {
int k = 0; memset(c, 0, sizeof c);
for (int j = i; j <= m; j ++) c[++ k] = b[j];
c[++ k] = '#';
for (int j = 1; j <= n; j ++) c[++ k] = a[j];
for (int j = 1; j <= k; j ++) fail[j] = 0;
for (int j = 2, t = 0; j <= k; j ++) {
while (t && c[t + 1] != c[j]) t = fail[t];
if (c[t + 1] == c[j]) fail[j] = ++ t;
}
for (int j = 1; j <= k; j ++) cnt[j] = 1;
for (int j = k; j >= 1; j --) cnt[fail[j]] += cnt[j];
for (int j = 1; j <= m - i + 1; j ++) sum[m - i - j + 2][m - i + 1] += cnt[j];
for (int j = 1; j <= m - i + 1; j ++) fail[j] = 0;
for (int j = 2, t = 0; j <= m - i + 1; j ++) {
while (t && c[t + 1] != c[j]) t = fail[t];
if (c[t + 1] == c[j]) fail[j] = ++ t;
}
for (int j = 1; j <= m - i + 1; j ++) cnt[j] = 1;
for (int j = m - i + 1; j >= 1; j --) cnt[fail[j]] += cnt[j];
for (int j = 1; j <= m - i + 1; j ++) sum[m - i - j + 2][m - i + 1] -= cnt[j];
}
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= i; j ++)
sum[j][i] += sum[j - 1][i];
for (int i = 1; i <= m; i ++)
for (int j = i + 1; j <= m; j ++)
ans += sum[i + min(lcp[i][j], j - i - 1)][j - 1] - sum[i][j - 1];
return printf("%lld\n", ans), 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 302772kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 7ms
memory: 302708kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 4ms
memory: 302840kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 8ms
memory: 302652kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 11ms
memory: 302772kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1161
result:
ok 1 number(s): "1161"
Test #6:
score: 0
Accepted
time: 1068ms
memory: 302900kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
78156256250000
result:
ok 1 number(s): "78156256250000"
Test #7:
score: 0
Accepted
time: 28ms
memory: 302884kb
input:
gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...
output:
60716448
result:
ok 1 number(s): "60716448"
Test #8:
score: 0
Accepted
time: 27ms
memory: 302816kb
input:
mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...
output:
60679828
result:
ok 1 number(s): "60679828"
Test #9:
score: 0
Accepted
time: 775ms
memory: 302800kb
input:
vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...
output:
2655796915
result:
ok 1 number(s): "2655796915"
Test #10:
score: 0
Accepted
time: 793ms
memory: 302808kb
input:
ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...
output:
2652657341
result:
ok 1 number(s): "2652657341"
Test #11:
score: 0
Accepted
time: 801ms
memory: 302896kb
input:
uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...
output:
2619083676
result:
ok 1 number(s): "2619083676"
Test #12:
score: 0
Accepted
time: 28ms
memory: 302880kb
input:
ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...
output:
61227979
result:
ok 1 number(s): "61227979"
Test #13:
score: 0
Accepted
time: 154ms
memory: 302880kb
input:
cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...
output:
834307544
result:
ok 1 number(s): "834307544"
Test #14:
score: 0
Accepted
time: 797ms
memory: 302816kb
input:
trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...
output:
2663862697
result:
ok 1 number(s): "2663862697"
Test #15:
score: 0
Accepted
time: 31ms
memory: 302860kb
input:
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 1072ms
memory: 302880kb
input:
igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...
output:
1707132
result:
ok 1 number(s): "1707132"
Test #17:
score: 0
Accepted
time: 52ms
memory: 302868kb
input:
jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...
output:
2954810
result:
ok 1 number(s): "2954810"
Test #18:
score: 0
Accepted
time: 36ms
memory: 302876kb
input:
juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...
output:
40401
result:
ok 1 number(s): "40401"
Test #19:
score: 0
Accepted
time: 980ms
memory: 302896kb
input:
lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...
output:
1421341
result:
ok 1 number(s): "1421341"
Test #20:
score: 0
Accepted
time: 48ms
memory: 302872kb
input:
cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...
output:
3118221
result:
ok 1 number(s): "3118221"
Test #21:
score: 0
Accepted
time: 1399ms
memory: 302908kb
input:
srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...
output:
75529025
result:
ok 1 number(s): "75529025"
Test #22:
score: 0
Accepted
time: 986ms
memory: 302896kb
input:
onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...
output:
3326939
result:
ok 1 number(s): "3326939"
Test #23:
score: 0
Accepted
time: 34ms
memory: 302796kb
input:
etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...
output:
547040
result:
ok 1 number(s): "547040"
Test #24:
score: 0
Accepted
time: 47ms
memory: 302876kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
38791844792
result:
ok 1 number(s): "38791844792"
Test #25:
score: 0
Accepted
time: 239ms
memory: 302832kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
4804791846049
result:
ok 1 number(s): "4804791846049"
Test #26:
score: 0
Accepted
time: 942ms
memory: 302880kb
input:
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...
output:
10043476749324
result:
ok 1 number(s): "10043476749324"
Test #27:
score: 0
Accepted
time: 557ms
memory: 302892kb
input:
yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...
output:
269398620
result:
ok 1 number(s): "269398620"
Test #28:
score: 0
Accepted
time: 524ms
memory: 302908kb
input:
yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...
output:
269769773
result:
ok 1 number(s): "269769773"
Test #29:
score: 0
Accepted
time: 520ms
memory: 302808kb
input:
baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...
output:
287077563
result:
ok 1 number(s): "287077563"
Extra Test:
score: 0
Extra Test Passed