QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246124#4669. Genetic ModificationszqsWA 0ms1408kbC++141.6kb2023-11-10 16:22:422023-11-10 16:22:43

Judging History

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

  • [2023-11-10 16:22:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1408kb
  • [2023-11-10 16:22:42]
  • 提交

answer

#include <cstdio>
#include <cstring>

char S[100005], T[100005];
int p1[100005], p2[100005], nxt[100005][2], pre[100005][2], len1, len2, n, m;
int ans[100005], len;
int getmost(int k) {
	if (!k) return len1 = 0;
	len1 = 0, nxt[k + 1][0] = nxt[k + 1][1] = k + 1;
	for (int i = k; i; -- i)
		nxt[i][0] = nxt[i + 1][0], nxt[i][1] = nxt[i + 1][1], nxt[i][S[i] - '0'] = i;
	int j = 0;
	for (int i = 1; i <= k && j < m; ++ i) {
		int p = nxt[i][T[j + 1] - '0'];
		if (p <= k) ++ j, p1[++ len1] = i = p;
		else break;
	}
	return len1;
}
int getleast(int k) {
	if (k > n) return len2 = 0;
	len2 = 0;
	int now = m;
	for (int i = n; i >= k; -- i) {
		int j = i;
		while (j > k && S[j - 1] == S[i]) -- j;
		if (j != k && !now) return 1e9;
		if (S[i] == T[now]) p2[++ len2] = i = j, -- now;
		else if (j > k) p2[++ len2] = i = j - 1, -- now;
		else break;
	}
	return len2;
}
bool check() {
	ans[0] = 0, ans[len + 1] = n + 1;
	for (int i = 0; i <= len; ++ i)
	for (int j = ans[i] + 1; j < ans[i + 1]; ++ j)
		if (S[j] != S[ans[i] + 1]) return false;
	return true;
}

int main() {
	scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), m = strlen(T + 1);
	if (getmost(n) < m || getleast(1) > m) return puts("NO"), 0;
	int l = 0, r = n;
	while (l < r) {
		int mid = l + r >> 1;
		if (getmost(mid) + getleast(mid + 1) >= m) r = mid;
		else l = mid + 1;
	}
	if (getmost(l) + getleast(l + 1) != m) return puts("NO"), 0;
	for (int i = 1; i <= len1; ++ i) ans[++ len] = p1[i];
	while (len2) ans[++ len] = p2[len2 --];
	if (check()) {
		puts("YES");
		for (int i = 1; i <= len; ++ i) printf("%d ", ans[i]);
	} else puts("NO");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

BBAAABBAAABAAA
BAAB

output:

NO

result:

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