QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280030#7780. Dark LaTeX vs. Light LaTeXucup-team1198#WA 0ms3880kbC++143.0kb2023-12-09 13:27:182023-12-09 13:27:18

Judging History

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

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2023-12-09 13:27:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2023-12-09 13:27:18]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> get_pi(string s) {
  vector<int> pi(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = pi[i - 1];
    while (j != -1 && s[i] != s[j])
      j = j == 0 ? -1 : pi[j - 1];
    pi[i] = j + 1;
  }
  return pi;
}

vector<int> get_z(string s) {
  vector<int> z(s.size());
  int j = 0;
  for (int i = 1; i < s.size(); ++i) {
    if (j + z[j] > i)
      z[i] = min(j + z[j] - i, z[i - j]);
    while (s[i + z[i]] == s[z[i]])
      ++z[i];
    if (i + z[i] > j + z[j])
      j = i;
  }
  return z;
}

int main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  string s;
  string t;
  cin >> s >> t;
  vector<vector<int>> s_pi(s.size());
  for (int i = 0; i < s.size(); ++i) {
    string cur = s.substr(i, s.size() - i) + '$' + s;
    auto tmp = get_pi(cur);
    vector<int> sum(tmp.size());
    for (int j = 0; j < tmp.size(); ++j) {
      if (tmp[j] == 0)
        sum[j] = 0;
      else
        sum[j] = 1 + sum[tmp[j] - 1];
    }
    s_pi[i].resize(s.size());
    for (int j = 0; j < s.size(); ++j)
      s_pi[i][j] = tmp[s.size() - i + 1 + j];
  }
  vector<vector<int>> t_pi(t.size());
  for (int i = 0; i < t.size(); ++i) {
    string cur = t.substr(i, t.size() - i) + '$' + t;
    auto tmp = get_pi(cur);
    vector<int> sum(tmp.size());
    for (int j = 0; j < tmp.size(); ++j) {
      if (tmp[j] == 0)
        sum[j] = 0;
      else
        sum[j] = 1 + sum[tmp[j] - 1];
    }
    t_pi[i].resize(t.size());
    for (int j = 0; j < t.size(); ++j)
      t_pi[i][j] = tmp[t.size() - i + 1 + j];
  }

  long long ans = 0;
  for (int i = 0; i < s.size(); ++i) {
    auto tmp = get_z(s.substr(i, s.size() - i) + '$' + t);
    vector<int> cnts(s.size() + 1);
    for (int j = 0; j < t.size(); ++j)
      ++cnts[tmp[s.size() - i + 1 + j]];
    for (int j = int(s.size()) - 1; j >= 0; --j)
      cnts[j] += cnts[j + 1];
    for (int j = i; j < s.size(); ++j) {
      ans += cnts[j - i + 1];
      if (j + 1 < s.size() && i > 0)
        ans += cnts[j - i + 1] * 1ll * s_pi[j + 1][i - 1];
    }
  }
  for (int i = 0; i < t.size(); ++i) {
    auto tmp = get_z(t.substr(i, t.size() - i) + '$' + s);
    vector<int> cnts(t.size() + 1);
    for (int j = 0; j < s.size(); ++j)
      ++cnts[tmp[t.size() - i + 1 + j]];
    for (int j = int(t.size()) - 1; j >= 0; --j)
      cnts[j] += cnts[j + 1];
    for (int j = i; j < t.size(); ++j) {
      if (j + 1 < t.size() && i > 0)
        ans += cnts[j - i + 1] * 1ll * t_pi[j + 1][i - 1];
    }
  }
  cout << ans << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

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

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

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

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1488

result:

wrong answer 1st numbers differ - expected: '1161', found: '1488'