QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246162#4669. Genetic ModificationsMYFJCHCWA 1ms4088kbC++141.1kb2023-11-10 16:46:362023-11-10 16:46:37

Judging History

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

  • [2023-11-10 16:46:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4088kb
  • [2023-11-10 16:46:36]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m;
char s[N], t[N];
int nxt[N], f[N], g[N];

int main()
{
	scanf("%s%s", s + 1, t + 1);
	n = strlen(s + 1), m = strlen(t + 1);
	for(int i = 1; i <= n; i ++ ) nxt[i] = s[i] == s[i - 1] ? nxt[i - 1] : i - 1;
//	for(int i = 1; i <= n; i ++ ) printf("%d ", nxt[i]);
//	puts("");
	g[m + 1] = n + 1;
	for(int i = m, j = n; i > 0 && j > 0; i -- , j -- )
	{
		if(t[i] != s[j]) j = nxt[j];
		else j = nxt[j] + 1;
		if(j > 0) g[i] = j;
	}
	if(g[1] && nxt[g[1] - 1] == 0)
	{
		puts("YES");
		for(int k = 1; k <= m; k ++ ) printf("%d ", g[k]);
		return 0;
	}
	for(int i = 1, j = 1; i <= m && j <= n; i ++ , j ++ )
	{
		while(j <= m && t[i] != s[j]) j ++ ;
		f[i] = j;
		if(j <= m && g[j + 1] && nxt[g[j + 1] - 1] <= j)
		{
			puts("YES");
			for(int k = 1; k <= i; k ++ ) printf("%d ", f[k]);
			for(int k = i + 1; k <= m; k ++ ) printf("%d ", g[k]);
			return 0;
		}
	}
//	for(int i = 1; i <= m; i ++ ) printf("%d ", f[i]);
//	puts("");
//	for(int i = 1; i <= m; i ++ ) printf("%d ", g[i]);
//	puts("");
	puts("NO");
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

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

input:

ABABABABAB
ABAB

output:

NO

result:

ok no solution

Test #3:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...

output:

NO

result:

ok no solution

Test #4:

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

input:

BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...

output:

YES
1 2 4 5 6 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 63 64 66 67 69 70 71 72 73 74 75 76 77 78 79 80 81 83 85 86 87 88 89 90 91 92 95 96 97 98 99 100 101 102 104 105 106 107 108 109 110 11...

result:

wrong answer Integer 0 violates the range [1, 13058]