QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#673605	#7780. Dark LaTeX vs. Light LaTeX	Kotomi	TL	895ms	269348kb	C++17	8.1kb	2024-10-25 01:39:29	2024-10-25 01:39:29

Judging History

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

[2024-11-25 20:53:52]
hack成功，自动添加数据
(/hack/1258)

[2024-10-25 01:39:29]
评测

测评结果：TL
用时：895ms
内存：269348kb

查看

[2024-10-25 01:39:29]
提交

answer

#include <bits/stdc++.h>

#define multi_test 0
#define DEBUG 0
#define MADE_IN_HEAVEN

#ifdef MADE_IN_HEAVEN
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#endif

using LL = long long;
using PII = std::pair<int, int>;
using ULL = unsigned long long;

constexpr int N = 5e3 + 10, base = 1331;
ULL p[N];
char s[N], t[N];
int f[N][N];
LL g[N][N];
bool added;

struct hash_handler {
  ULL h[N];

  void init(char *s) {
    h[0] = 0;
    for (int i = 1; s[i - 1]; ++i) {
      h[i] = h[i - 1] * base + s[i - 1];
    }
  }

  ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
} sh, th;

void pre_work() {
  p[0] = 1;
  for (int i = 1; i < N; ++i) {
    p[i] = p[i - 1] * base;
  }
}

LL solve(char *s, char *t, int n, int m) {
  int N = n + 10;
  sh.init(s);
  th.init(t);

  std::unordered_map<ULL, int> cntt;
  for (int i = 1; i <= m; ++i) {
    for (int j = i; j <= m; ++j) {
      cntt[th.get(i, j)]++;
    }
  }

  LL ans = 0;
  if (not added) {
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        auto h = sh.get(i, j);
        if (cntt.count(h)) {
          ans += cntt[h];
        }
      }
    }
    added = true;
  }

  for (int i = n; i >= 1; --i) {
    for (int j = n; j >= i; --j) {
      if (s[i - 1] == s[j - 1]) {
        f[i][j] = i + 1 <= n and j + 1 <= n ? f[i + 1][j + 1] + 1 : 1;
      } else {
        f[i][j] = 0;
      }
    }
  }

  // g[i][j] 表示 s[i,j] 的所有后缀在 t 中出现的次数
  for (int j = n; j >= 1; --j) {
    for (int i = j; i >= 1; --i) {
      if (i == j) {
        g[i][j] = cntt[sh.get(i, j)];
      } else {
        g[i][j] = g[i + 1][j] + cntt[sh.get(i, j)];
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = i + 2; j <= n; ++j) {
      if (not f[i][j])
        continue;
      int pos = i + f[i][j];
      ans += g[i + 1][j - 1];
      if (pos + 1 < j) {
        ans -= g[pos + 1][j - 1];
      }
    }
  }

  return ans;
}

int main() {
  if constexpr (DEBUG) {
    std::cerr.tie(nullptr);
    freopen("data.in", "r", stdin);
  }

  pre_work();

  scanf("%s%s", s, t);

  int n = strlen(s), m = strlen(t);
  auto res = solve(s, t, n, m);

  std::reverse(s, s + n);
  std::reverse(t, t + m);

  res += solve(t, s, m, n);
  printf("%lld\n", res);
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 7964kb

input:

abab
ab

output:

result:

ok 1 number(s): "8"

Test #2:

score: 0

Accepted

time: 1ms

memory: 6152kb

input:

abab
abaaab

output:

result:

ok 1 number(s): "29"

Test #3:

score: 0

Accepted

time: 1ms

memory: 6208kb

input:

abcd
abcde

output:

result:

ok 1 number(s): "10"

Test #4:

score: 0

Accepted

time: 1ms

memory: 7964kb

input:

aaba
ba

output:

result:

ok 1 number(s): "6"

Test #5:

score: 0

Accepted

time: 1ms

memory: 8000kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

result:

ok 1 number(s): "1161"

Test #6:

score: 0

Accepted

time: 895ms

memory: 269348kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0

Accepted

time: 159ms

memory: 81140kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0

Accepted

time: 145ms

memory: 80228kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: -100

Time Limit Exceeded

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...