QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#86178#5256. Insertions5abWA 1ms3380kbC++174.2kb2023-03-09 14:52:562023-03-09 14:53:17

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-09 14:53:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3380kb
  • [2023-03-09 14:52:56]
  • 提交

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'