QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721333#9406. TriangleguosounWA 1ms3680kbC++175.3kb2024-11-07 15:53:002024-11-07 15:53:01

Judging History

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

  • [2024-11-07 15:53:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3680kb
  • [2024-11-07 15:53:00]
  • 提交

answer

#include <bits/stdc++.h>
// #include "../cpp-dump/cpp-dump.hpp"
template <class T>
void chkmin(T &x, const T &y) {
  if (x > y) x = y;
}
template <class T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
using ll = long long;
using std::cerr;

struct suffix_array {
  std::vector<int> sa, rk;
  std::array<std::vector<int>, 20> st;
  suffix_array(std::vector<int> a) {
    int n = a.size();
    sa.resize(n), rk.resize(n * 2, -1);
    std::vector<int> tmp(n), cnt(n);

    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int x, int y) { return a[x] < a[y]; });
    rk[sa[0]] = 0;
    for (int i = 1; i < n; i++)
      rk[sa[i]] = rk[sa[i - 1]] + (a[sa[i]] != a[sa[i - 1]]);
    for (int w = 1;; w <<= 1) {
      int l = 0;
      for (int i = n - w; i < n; i++) tmp[l++] = i;
      for (int i = 0; i < n; i++)
        if (sa[i] >= w) tmp[l++] = sa[i] - w;
      for (int i = 0; i < n; i++) {
        cnt[rk[sa[i]]] = i;
      }
      for (int i = n - 1; i >= 0; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
      tmp[sa[0]] = 0;
      for (int i = 1; i < n; i++)
        tmp[sa[i]] = tmp[sa[i - 1]] + (rk[sa[i - 1]] != rk[sa[i]] ||
                                       rk[sa[i - 1] + w] != rk[sa[i] + w]);
      std::copy_n(tmp.begin(), n, rk.begin());
      if (rk[sa[n - 1]] == n - 1) break;
    }

    st[0].resize(n), rk.resize(n), a.push_back(-1);
    for (int i = 0, k = 0; i < n; i++) {
      if (k) k--;
      if (rk[i] == 0) continue;
      while (a[i + k] == a[sa[rk[i] - 1] + k]) k++;
      st[0][rk[i]] = k;
    }
    for (int i = 1; i < 20; i++) {
      st[i].resize(n);
      for (int j = 0; j + (1 << i) - 1 < n; j++)
        st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
  int lcp(int i, int j) {
    if (i == j) return (int)sa.size() - i;
    i = rk[i], j = rk[j];
    if (i > j) std::swap(i, j);
    i++;
    int k = std::__lg(j - i + 1);
    return std::min(st[k][i], st[k][j - (1 << k) + 1]);
  }
};

void mian() {
  int n;
  std::cin >> n;
  std::vector<std::string> s(n);
  std::vector<int> ve, idx(n), len(n);
  for (int i = 0; i < n; i++) {
    std::cin >> s[i];
    ve.push_back(1e9 + i), idx[i] = ve.size();
    for (char c : s[i]) ve.push_back(c);
    len[i] = s[i].size(), s[i].push_back('-');
  }
  suffix_array sa(ve);
  auto cmp = [&](int i, int j, int p = 0) {
    int l = sa.lcp(idx[i] + p, idx[j]);
    return s[i][l + p] < s[j][l];
  };
  auto cmp2 = [&](int c, std::pair<int, int> d) {  // c < a + b
    auto [a, b] = d;
    if (sa.lcp(idx[a], idx[c]) == len[a])
      return cmp(c, b, len[a]);
    return cmp(c, a);
  };
  std::vector<int> id(n);
  std::iota(id.begin(), id.end(), 0);
  std::sort(id.begin(), id.end(), cmp);
  // cpp_dump(id);
  auto find = [&](int i) -> std::pair<int, int> {
    auto p = std::upper_bound(id.begin(), id.end(), i, cmp) - id.begin();
    int l = len[i];
    if (p == n || sa.lcp(idx[p], idx[i]) != l) return std::make_pair(0, -1);
    int pp = p;
    for (int i = 20; ~i; i--)
      if (pp + (1 << i) < n && sa.lcp(idx[pp + (1 << i)], idx[i]) == l)
        pp += 1 << i;
    return std::make_pair(p, pp);
  };
  std::vector<int> uid;
  std::unordered_map<std::string, int> mp;
  for (int i : id) {
    if (mp.count(s[i]))
      mp[s[i]] += 1;
    else
      mp[s[i]] = 1, uid.push_back(i);
  }
  ll ans = 0;
  for (int i : uid) {
    auto t =
        std::lower_bound(id.begin(), id.end(), std::make_pair(i, i), cmp2) -
        id.begin();
    ans += (ll)mp[s[i]] * (mp[s[i]] - 1) / 2 * t;
    ans -= (ll)mp[s[i]] * (mp[s[i]] - 1) * (mp[s[i]] - 2) / 6 * 2;
  }
  for (int i = 0; i < (int)uid.size(); i++) {
    int a = uid[i];
    for (int j = i + 1; j < (int)uid.size(); j++) {
      int b = uid[j];
      if (sa.lcp(idx[a], idx[b]) != len[a]) break;
      auto [l1, r1] = find(b);
      chkmin<int>(r1, std::max(std::lower_bound(id.begin(), id.end(),
                                                std::make_pair(a, b), cmp2) -
                                   id.begin() - 1,
                               std::lower_bound(id.begin(), id.end(),
                                                std::make_pair(b, a), cmp2) -
                                   id.begin() - 1));
      ans += std::max(r1 - l1 + 1, 0);
      auto [l2, r2] = find(a);
      chkmax<int>(l2, std::upper_bound(id.begin(), id.end(), b, cmp) - id.begin());
      chkmin<int>(r2, std::max(std::lower_bound(id.begin(), id.end(),
                                                std::make_pair(a, b), cmp2) -
                                   id.begin() - 1,
                               std::lower_bound(id.begin(), id.end(),
                                                std::make_pair(b, a), cmp2) -
                                   id.begin() - 1));
      ans += std::max(r2 - l2 + 1, 0);
      auto [l3, r3] = std::pair<int, int>(0, std::lower_bound(id.begin(), id.end(), a, cmp) - id.begin() - 1);
      chkmax<int>(l3, std::upper_bound(id.begin(), id.end(), b, [&](auto x, auto y) {
               return cmp(x, y, len[a]);
             }) - id.begin());
      ans += std::max(r3 - l3 + 1, 0);
    }
  }
  std::cout << ans << '\n';
}
int main() { 
  std::cin.tie(0)->sync_with_stdio(0); 
  int t;
  std::cin >> t;
  while (t--) mian();
}

詳細信息

Test #1:

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

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

16
0
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3668kb

input:

14
1
lfpbavjsm
2
pdtlkfwn
mbd
3
dvqksg
dvqksg
uhbhpyhj
4
ombwb
ombwb
ombwb
ombwb
5
oztclz
oztclz
oztclz
oztclz
kul
6
vco
vco
vco
dtktsqtinm
vco
vco
7
tb
tb
kowbsu
ygkfphcij
tb
uvei
tb
8
vxxtxssht
abnsxbf
bydaae
bydaae
udalyvmcef
bydaae
bydaae
bydaae
9
aaze
zvyonw
qjfv
mmhkef
qjfv
qjfv
qjfv
mmhkef
qj...

output:

0
0
2
16
22
40
22
40
63
30
35
98
26
11769

result:

wrong answer 3rd lines differ - expected: '0', found: '2'