QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#245939#4669. Genetic ModificationsNightmare07WA 0ms9960kbC++142.6kb2023-11-10 14:42:082023-11-10 14:42:08

Judging History

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

  • [2023-11-10 14:42:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9960kb
  • [2023-11-10 14:42:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2010;
const int K = 25;

int n, m, tmp;
int f[N], Pre[N], G[M][M], G_[N][K], c[N];
bool dp[M][M], dp_[N][K];
char a[N], b[N];

int Find(int x) {
	if (f[x] != x) f[x] = Find(f[x]);
	return f[x];
}

int main() {
	scanf("%s%s", a + 1, b + 1);
	
	n = strlen(a + 1), m = strlen(b + 1);
	
	for (int i = 1; i <= n; i ++) f[i] = i;
	for (int i = 2; i <= n; i ++)
		if (a[i - 1] == a[i]) {
			int fx = Find(i - 1), fy = Find(i);
			f[fy] = fx;
		}
	
	for (int i = 1; i <= n; i ++) {
		if (i == 1) Pre[i] = 0;
		else if (a[i - 1] == a[i]) Pre[i] = max(1, Find(i) - 1);
		else Pre[i] = max(1, Find(i - 1) - 1);
	}
	
	if (n <= 2000) {
		for (int i = 1; i <= n; i ++)
			if (a[i] == b[1]) dp[i][1] = 1;
		for (int j = 2; j <= m; j ++) {
			int cnt = 0;
			dp[1][j] = 0;
			queue<int> q;
			for (int i = 2; i <= n; i ++) {
				if (dp[i - 1][j - 1]) q.push(i - 1);
				if (a[i] == b[j]) {
					if (q.size() && q.front() < Pre[i]) q.pop();
					if (q.size()) dp[i][j] = 1, G[i][j] = q.front();
				}
			}
		}
		int Id = 0;
		for (int i = 1; i <= n; i ++) {
			if (dp[i][m]) {
				Id = i;
				break;
			}
		}
		if (!Id) puts("NO");
		else {
			puts("YES");
			stack<int> s;
			for (int i = m; i >= 1; i --) {
				s.push(Id);
				Id = G[Id][i];
				if (i == 1) break;
			}
			while (s.size()) {
				printf("%d ", s.top());
				s.pop();
			}
		}
		return 0;
	}
	
	if (m <= 20) {
		for (int i = 1; i <= n; i ++)
			if (a[i] == b[1]) dp_[i][1] = 1;
		for (int j = 2; j <= m; j ++) {
			int cnt = 0;
			dp_[1][j] = 0;
			queue<int> q;
			for (int i = 2; i <= n; i ++) {
				if (dp_[i - 1][j - 1]) q.push(i - 1);
				if (a[i] == b[j]) {
					if (q.size() && q.front() < Pre[i]) q.pop();
					if (q.size()) dp_[i][j] = 1, G_[i][j] = q.front();
				}
			}
		}
		int Id = 0;
		for (int i = 1; i <= n; i ++) {
			if (dp_[i][m]) {
				Id = i;
				break;
			}
		}
		if (!Id) puts("NO");
		else {
			puts("YES");
			stack<int> s;
			for (int i = m; i >= 1; i --) {
				s.push(Id);
				Id = G_[Id][i];
				if (i == 1) break;
			}
			while (s.size()) {
				printf("%d ", s.top());
				s.pop();
			}
		}
		return 0;
	}
	
	c[1] = 1, tmp = 1;
	for (int i = 2; i <= n; i ++)
		if (a[i] != a[i - 1]) c[++ tmp] = i;
	
	if (a[1] != b[1]) {
		if (tmp - 1 >= m) {
			puts("YES");
			for (int i = 2; i <= m + 1; i ++) printf("%d ", c[i]);
		}
		else puts("NO");
	}
	else {
		if (tmp >= m) {
			puts("YES");
			for (int i = 1; i <= m; i ++) printf("%d ", c[i]);
		}
		else puts("NO");
	}
	
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9960kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
1 3 4 6 

result:

wrong answer wrong solution [2]