QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#64168 | #4669. Genetic Modifications | zimindaada | WA | 2ms | 3424kb | C++14 | 1.3kb | 2022-11-24 10:55:25 | 2022-11-24 10:55:27 |
Judging History
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;
}
詳細信息
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]