QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280582#7780. Dark LaTeX vs. Light LaTeXucup-team1191#AC ✓1422ms296744kbC++232.3kb2023-12-09 17:06:332024-11-25 21:01:33

Judging History

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

  • [2024-11-25 21:01:33]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1422ms
  • 内存:296744kb
  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2023-12-09 17:06:33]
  • 评测
  • 测评结果:100
  • 用时:1495ms
  • 内存:296840kb
  • [2023-12-09 17:06:33]
  • 提交

answer

#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> vector<int> z_function(int n, const T &s) {
  vector<int> z(n, n);
  int l = 0, r = 0;
  for (int i = 1; i < n; i++) {
    z[i] = (i > r ? 0 : min(r - i + 1, z[i - l]));
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
      z[i]++;
    }
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

template <typename T> vector<int> z_function(const T &s) {
  return z_function((int)s.size(), s);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int n = (int)s.size();
  int m = (int)t.size();
  ll ans = 0;
  for (int tt = 0; tt < 2; ++tt) {
    vector<vector<int>> cnt_occ(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      string cur = s.substr(i);
      cur += '#';
      int cur_size = (int)cur.size();
      cur += t;
      vector<int> z = z_function(cur);
      for (int j = 0; j < m; ++j) {
        if (z[cur_size + j] > 0) {
          ++cnt_occ[i][i + z[cur_size + j] - 1];
        }
      }
      for (int j = n - 2; j >= 0; --j) {
        cnt_occ[i][j] += cnt_occ[i][j + 1];
      }
    }
    vector<vector<int>> mem_cnt(n, vector<int>(2 * n));
    for (int i = 0; i < n; ++i) {
      string cur = s.substr(i);
      cur += '#';
      int cur_size = (int)cur.size();
      cur += s;
      vector<int> z = z_function(cur);
      for (int j = 0; j < n; ++j) {
        ++mem_cnt[i][j + z[cur_size + j]];
      }
      for (int j = 2 * n - 2; j >= 0; --j) {
        mem_cnt[i][j] += mem_cnt[i][j + 1];
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        if (tt == 0) {
          ans += cnt_occ[i][j];
        }
        if (j + 1 < n) {
          int extra = mem_cnt[j + 1][i] - (n - i);
          ans += (ll)extra * cnt_occ[i][j];
        }
      }
    }
    swap(s, t);
    swap(n, m);
  }
  cout << ans << '\n';
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

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

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

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

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

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

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 918ms
memory: 296656kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 27ms
memory: 15200kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 31ms
memory: 15160kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: 0
Accepted
time: 876ms
memory: 296652kb

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:

2655796915

result:

ok 1 number(s): "2655796915"

Test #10:

score: 0
Accepted
time: 866ms
memory: 296624kb

input:

ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...

output:

2652657341

result:

ok 1 number(s): "2652657341"

Test #11:

score: 0
Accepted
time: 850ms
memory: 296684kb

input:

uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...

output:

2619083676

result:

ok 1 number(s): "2619083676"

Test #12:

score: 0
Accepted
time: 31ms
memory: 15024kb

input:

ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...

output:

61227979

result:

ok 1 number(s): "61227979"

Test #13:

score: 0
Accepted
time: 287ms
memory: 109068kb

input:

cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...

output:

834307544

result:

ok 1 number(s): "834307544"

Test #14:

score: 0
Accepted
time: 846ms
memory: 296744kb

input:

trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...

output:

2663862697

result:

ok 1 number(s): "2663862697"

Test #15:

score: 0
Accepted
time: 33ms
memory: 15048kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 895ms
memory: 296604kb

input:

igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...

output:

1707132

result:

ok 1 number(s): "1707132"

Test #17:

score: 0
Accepted
time: 48ms
memory: 15020kb

input:

jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...

output:

2954810

result:

ok 1 number(s): "2954810"

Test #18:

score: 0
Accepted
time: 25ms
memory: 15152kb

input:

juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...

output:

40401

result:

ok 1 number(s): "40401"

Test #19:

score: 0
Accepted
time: 755ms
memory: 296544kb

input:

lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...

output:

1421341

result:

ok 1 number(s): "1421341"

Test #20:

score: 0
Accepted
time: 51ms
memory: 15044kb

input:

cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...

output:

3118221

result:

ok 1 number(s): "3118221"

Test #21:

score: 0
Accepted
time: 1422ms
memory: 296696kb

input:

srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...

output:

75529025

result:

ok 1 number(s): "75529025"

Test #22:

score: 0
Accepted
time: 840ms
memory: 296632kb

input:

onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...

output:

3326939

result:

ok 1 number(s): "3326939"

Test #23:

score: 0
Accepted
time: 35ms
memory: 15016kb

input:

etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...

output:

547040

result:

ok 1 number(s): "547040"

Test #24:

score: 0
Accepted
time: 23ms
memory: 14908kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

38791844792

result:

ok 1 number(s): "38791844792"

Test #25:

score: 0
Accepted
time: 297ms
memory: 108944kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

4804791846049

result:

ok 1 number(s): "4804791846049"

Test #26:

score: 0
Accepted
time: 807ms
memory: 296648kb

input:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

10043476749324

result:

ok 1 number(s): "10043476749324"

Test #27:

score: 0
Accepted
time: 570ms
memory: 206388kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269398620

result:

ok 1 number(s): "269398620"

Test #28:

score: 0
Accepted
time: 588ms
memory: 211036kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269769773

result:

ok 1 number(s): "269769773"

Test #29:

score: 0
Accepted
time: 607ms
memory: 211140kb

input:

baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...

output:

287077563

result:

ok 1 number(s): "287077563"

Extra Test:

score: 0
Extra Test Passed