QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90121#5256. InsertionswhateverWA 4ms11996kbC++143.3kb2023-03-22 13:29:552023-03-22 13:29:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 13:29:56]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:11996kb
  • [2023-03-22 13:29:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;

int n, m, k;
int f[N], nxt[N], mch[N];
int ans = -1, cnt, mn, mx;
char s[N], t[N], p[N];

void cnext(int n, char *s, int *nxt) {
  for(int i = 2, j = 0; i <= n; i++) {
    while(j && s[j + 1] != s[i]) j = nxt[j];
    nxt[i] = j += s[j + 1] == s[i];
  }
}
void match(int n, int m, char *s, char *t, int *mch) { // return occ
  cnext(m, t, nxt);
  for(int i = 1, j = 0; i <= n; i++) {
    while(j && t[j + 1] != s[i]) j = nxt[j];
    mch[i] = j += t[j + 1] == s[i];
  }
}

namespace IN {
  void solve() {
    if(k >= m) return;
    match(m, k, t, p, mch);
    int occ = 0;
    for(int i = 1; i <= m; i++) occ += mch[i] == k;
    for(int i = 0; i <= n; i++) f[i] += occ;
  }
}

namespace OUT {
  int app[N], mchR[N];
  char sR[N], pR[N];
  vector<int> e[N];
  vector<pair<int, int>> buc[N];
  int dn, dfn[N], sz[N], c[N];
  void dfs(int id) {
    dfn[id] = ++dn, sz[id] = 1;
    for(int it : e[id]) dfs(it), sz[id] += sz[it];
  }
  void add(int x, int v) {
    while(x <= dn) c[x] += v, x += x & -x;
  }
  void add(int l, int r, int v) {
    add(l, v), add(r + 1, -v);
  }
  int query(int x) {
    int s = 0;
    while(x) s += c[x], x -= x & -x;
    return s;
  }
  void dfs2(int id) {
    int _id = id + m, l = 0, r = 0;
    if(_id <= k) l = dfn[k - _id], r = l + sz[k - _id] - 1;
    if(_id <= k && app[_id]) add(l, r, 1);
    for(auto _ : buc[id]) f[_.first] += query(dfn[_.second]);
    for(int it : e[id]) dfs2(it);
    if(_id <= k && app[_id]) add(l, r, -1);
  }
  void solve() {
    if(k < m) return;
    memcpy(sR, s, sizeof(s));
    memcpy(pR, p, sizeof(p));
    reverse(sR + 1, sR + n + 1);
    reverse(pR + 1, pR + k + 1);
    match(k, m, p, t, mch);
    for(int i = 1; i <= k; i++) app[i] = mch[i] == m;
    match(n, k, sR, pR, mchR);
    for(int i = 1; i <= k; i++) e[nxt[i]].push_back(i);
    dfs(0);
    for(int i = 0; i < k; i++) e[i].clear();
    match(n, k, s, p, mch);
    for(int i = 1; i <= k; i++) e[nxt[i]].push_back(i);
    for(int i = 0; i <= n; i++) buc[mch[i]].push_back({i, mchR[n - i]});
    dfs2(0);
  }
}

namespace CROSS {
  int sz[N];
  void solve() {
    memset(sz, 0, sizeof(sz)); // add this line
    match(k, m, p, t, mch);
    int v = mch[k];
    if(v == m) v = nxt[v];
    while(v) sz[k - v]++, v = nxt[v];
    match(n, k, s, p, mch);
    for(int i = 1; i <= k; i++) sz[i] += sz[nxt[i]];
    for(int i = 0, pre = 0; i <= n; i++) {
      pre += mch[i] == k;
      f[i] += sz[mch[i]] + pre;
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> s + 1 >> t + 1 >> p + 1;
  n = strlen(s + 1);
  m = strlen(t + 1);
  k = strlen(p + 1);
  IN::solve();
  OUT::solve();
  CROSS::solve();
  reverse(s + 1, s + n + 1);
  reverse(t + 1, t + m + 1);
  reverse(p + 1, p + k + 1);
  reverse(f, f + n + 1);
  CROSS::solve();
  reverse(f, f + n + 1);
  for(int i = 0; i <= n; i++) {
    if(f[i] > ans) ans = f[i], cnt = 1, mn = mx = i;
    else if(f[i] == ans) cnt++, mx = i;
  }
  cout << ans << " " << cnt << " " << mn << " " << mx << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ H.cpp -o H -std=c++14 -O2 -DALEX_WEI
*/

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 9400kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 11996kb

input:

z
zzkkzzkk
z

output:

6 2 0 1

result:

wrong answer 1st numbers differ - expected: '5', found: '6'