QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246301#4669. Genetic ModificationsNightmare07WA 1ms3724kbC++141.7kb2023-11-10 18:48:512023-11-10 18:48:51

Judging History

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

  • [2023-11-10 18:48:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2023-11-10 18:48:51]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int l[N], r[N], f[N];
char a[N], b[N];

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

bool check(int x, char c, int id) {
	if (a[x + 1] == c) return true;
	else if (Find(x + 1) != n) return true;
	else return false;
}

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 = n - 1; i >= 1; i --) {
		int fx = Find(i), fy = Find(i + 1);
		if (a[i] == a[i + 1]) f[fx] = fy;
	}
	
	if (a[1] == b[1]) {
		l[1] = 1;
		for (int i = 1; i <= n; i ++) {
			if (a[i] == b[1]) r[1] = i;
			else break;
		}
	}
	else {
		for (int i = 1; i <= n; i ++) {
			if (a[i] == b[i]) {
				l[1] = r[1] = i;
				break;
			}
		}
		if (!l[1]) {
			puts("NO");
			return 0;
		}
	}
	
	for (int i = 2; i <= m; i ++) {
		l[i] = l[i - 1];
		while (l[i] < n && !check(l[i], b[i], i - 1)) {
			while (l[i] + 1 <= n && a[l[i] + 1] != a[l[i - 1]]) l[i] ++;
			l[i] ++;
		}
		if (l[i] >= n) {
			puts("NO");
			return 0;
		}
		r[i] = max(r[i - 1], l[i]);
		if (a[l[i] + 1] == b[i]) l[i] ++;
		else l[i] = Find(l[i] + 1) + 1;
		while (r[i] + 1 <= n && check(r[i] + 1, a[i], i - 1)) {
			if (r[i] + 1 <= n && a[r[i] + 1] != a[l[i - 1]]) break;
			r[i] ++;
		}
		if (!check(r[i], a[i], i - 1)) {
			puts("NO");
			return 0;
		}
		if (a[r[i] + 1] == b[i]) r[i] = Find(r[i] + 1);
		else r[i] = Find(r[i] + 1) + 1;
	}
	
	for (int i = r[m] + 2; i <= n; i ++)
		if (a[i - 1] != a[i]) {
			puts("NO");
			return 0;
		}
	
	puts("YES");
	for (int i = 1; i <= m; i ++) printf("%d ", r[i]);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

ABABABABAB
ABAB

output:

NO

result:

ok no solution

Test #3:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...

output:

NO

result:

ok no solution

Test #4:

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

input:

BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...

output:

NO

result:

wrong answer you didn't find a solution but jury did