QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64168#4669. Genetic ModificationszimindaadaWA 2ms3424kbC++141.3kb2022-11-24 10:55:252022-11-24 10:55:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-24 10:55:27]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3424kb
  • [2022-11-24 10:55:25]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
namespace ztd{
    using namespace std;
    typedef long long ll;
    template<typename T> inline T read(T& t) {
        t=0;short f=1;char ch=getchar();
        while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
        while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
        t*=f; return t;
    }
}
using namespace ztd;
const int maxn = 1e5+7;
char s[maxn], t[maxn];
int n, m, o, p, pos[maxn], inbl[maxn];
struct node{int l, r;} a[maxn];
inline void NO(){
	puts("NO");
	exit(0);
}
inline void YES(){
	puts("YES");
	for(int i = 1; i <= m; ++i) cout << pos[i] << ' ';
	exit(0);
}
signed main(){
	scanf("%s\n%s",s+1,t+1);
	n = strlen(s+1); m = strlen(t+1);
	for(int i = 1; i <= n; ++i){
		int cnt = 1, j;
		for(j = i; j <= n; ++j){
			if(j == n || s[j+1] != s[i]) break;
		}
		a[++o] = (node){i, j};
		for(int p = i; p <= j; ++p) inbl[p] = o;
		i = j;
	}
	for(int i = 1; i <= n; ++i){
		if(s[i] == t[p+1]) pos[++p] = i;
	}
	if(p < m) NO(); 
	pos[p+1] = n+1;
	for(int i = m; i >= 1; --i){
		if(inbl[pos[i]+1] >= inbl[pos[i+1]-1]) YES();
		pos[i] = a[inbl[pos[i+1]-1]].l;
		if(s[pos[i]] != t[i]) --pos[i];
	}
	if(inbl[pos[1]-1] >= 1) YES();
	else NO();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3420kb

input:

ABABABABAB
ABAB

output:

YES
7 8 9 10 

result:

wrong answer wrong solution [2]