QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#86178 | #5256. Insertions | 5ab | WA | 1ms | 3380kb | C++17 | 4.2kb | 2023-03-09 14:52:56 | 2023-03-09 14:53:17 |
Judging History
answer
/* name: 5256
* author: 5ab
* created at: 2023-03-08
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int max_n = 5;
int ld[max_n + 1], rd[max_n + 1], cans[max_n + 1], fl[max_n * 2 + 1];
struct Tr
{
int hd[max_n + 1], st[max_n + 1], ed[max_n + 1], fa[max_n + 1], ind = 0;
int des[max_n], nxt[max_n], e_cnt = 0;
Tr() { memset(hd, -1, sizeof hd); }
void add(int s, int t)
{
des[e_cnt] = t;
nxt[e_cnt] = hd[s];
hd[s] = e_cnt++;
}
void dfs(int id)
{
st[id] = ind++;
for (int p = hd[id], dst; p != -1; p = nxt[p])
{
dst = des[p];
dfs(dst);
}
ed[id] = ind;
}
} T1, T2;
struct fwt
{
int tr[max_n + 2], n;
static inline int lowbit(int x) { return x & -x; }
void clear() { memset(tr, 0, sizeof tr); }
void add(int x, int v)
{
for (x++; x <= n; x += lowbit(x))
tr[x] += v;
}
int get(int x)
{
int res = 0;
for (x++; x; x -= lowbit(x))
res += tr[x];
return res;
}
} f;
char ts[max_n * 2 + 1];
vector<int> qr[max_n + 1];
int sl, tl, pl;
void getfail(int *fail, int n)
{
fail[0] = 0;
// cerr << ts << endl;
for (int i = 1, j = 0; i < n; i++)
{
while (j && ts[i] != ts[j]) j = fail[j - 1];
fail[i] = (j += (ts[i] == ts[j]));
}
// for (int i = 0; i < n; i++)
// cerr << fail[i] << " \n"[i == n - 1];
}
void buildtree(int n, Tr& tr)
{
tr.fa[0] = -1;
for (int i = 0; i < n; i++)
{
tr.add(fl[i], i + 1);
tr.fa[i + 1] = fl[i];
}
tr.dfs(0);
}
void solve1(Tr& t1, Tr& t2, int *d)
{
getfail(fl, tl + pl + 1);
int tx = fl[tl + pl];
for (int x = tx == min(pl, tl) ? t2.fa[tx] : tx; x != 0; x = t2.fa[x])
{
f.add(t1.st[pl - x], 1);
f.add(t1.ed[pl - x], -1);
// cerr << x << " " << t1.st[pl - x] << endl;
}
for (int i = 0; i <= sl; i++)
{
cans[i] += f.get(t1.st[d[i]]);
// cerr << d[i] << "," << t1.st[d[i]] << " \n"[i == sl];
}
f.clear();
for (int i = 0; i <= sl; i++)
cerr << cans[i] << " \n"[i == sl];
}
void solve2(int x)
{
if (x + tl <= pl && fl[tl + tl + x] == tl)
{
f.add(T2.st[pl - tl - x], 1);
f.add(T2.ed[pl - tl - x], -1);
}
for (int qry : qr[x])
cans[qry] += f.get(T2.st[rd[qry]]);
for (int p = T1.hd[x]; p != -1; p = T1.nxt[p])
solve2(T1.des[p]);
if (x + tl <= pl && fl[tl + tl + x] == tl)
{
f.add(T2.st[pl - tl - x], -1);
f.add(T2.ed[pl - tl - x], 1);
}
}
char s[max_n + 1], t[max_n + 1], p[max_n + 1];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t >> p;
sl = strlen(s), tl = strlen(t), pl = strlen(p), f.n = pl + 1;
copy(s, s + sl, copy(p, p + pl, ts) + 1), ts[pl] = '$';
getfail(fl, sl + pl + 1);
buildtree(pl, T1);
copy(fl + pl, fl + sl + pl + 1, ld);
int bsn = 0;
for (int i = pl; i <= sl; i++)
bsn += (ld[i] == pl);
for (int i = 0; i <= sl; i++)
{
bsn += (ld[i] == pl);
cans[i] += bsn;
if (i + pl <= sl)
bsn -= (ld[i + pl] == pl);
}
copy(p, p + pl, copy(s, s + sl, ts) + 1), ts[sl] = '$';
reverse(ts, ts + pl + sl + 1);
getfail(fl, sl + pl + 1);
buildtree(pl, T2);
copy(fl + pl, fl + sl + pl + 1, rd);
reverse(rd, rd + sl + 1);
copy(p, p + pl, copy(t, t + tl, ts) + 1), ts[tl] = '$';
solve1(T1, T2, ld);
copy(t, t + tl, copy(p, p + pl, ts) + 1), ts[pl] = '$';
solve1(T2, T1, rd);
if (pl <= tl)
{
int ans = -1, lmx = -1, rmx = -1, cnt = 0;
for (int i = 0; i <= sl; i++)
if (cans[i] > ans)
lmx = rmx = i, ans = cans[i], cnt = 1;
else if (ans == cans[i])
rmx = i, cnt++;
for (int i = 0; i < tl; i++)
ans += (fl[pl + i + 1] == pl);
cout << ans << " " << cnt << " " << lmx << " " << rmx << endl;
return 0;
}
copy(p, p + pl, copy(t, t + tl, ts) + 1), ts[tl] = '$';
getfail(fl, tl + pl + 1);
for (int i = 0; i <= sl; i++)
qr[ld[i]].push_back(i);
solve2(0);
int ans = -1, lmx = -1, rmx = -1, cnt = 0;
for (int i = 0; i <= sl; i++)
if (cans[i] > ans)
lmx = rmx = i, ans = cans[i], cnt = 1;
else if (ans == cans[i])
rmx = i, cnt++;
cout << ans << " " << cnt << " " << lmx << " " << rmx << endl;
return 0;
}
// started coding at: 03-08 18:01:14
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3380kb
input:
rrddrrrdd ddrrd rrddrr
output:
1 2 0 4
result:
wrong answer 1st numbers differ - expected: '2', found: '1'