QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246299 | #4669. Genetic Modifications | Judgelight | WA | 1ms | 5808kb | C++14 | 1.1kb | 2023-11-10 18:47:52 | 2023-11-10 18:47:52 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
char a[N],b[N];
int n,m,nex[N][2],pre[N][2];
int mark[N],mrk[N];
bool vis[N];
int main(){
scanf("%s%s",a+1,b+1);
n=strlen(a+1),m=strlen(b+1);
for(int i=1;i<=n;++i)a[i]^=48;
for(int i=1;i<=m;++i)b[i]^=48;
for(int i=n;i>=1;--i){
nex[i][a[i]]=i;
nex[i][a[i]^1]=nex[i+1][a[i]^1];
}
for(int i=1;i<=n;++i){
pre[i][a[i]]=i;
pre[i][a[i]^1]=pre[i-1][a[i]^1];
}
for(int i=1,j=1;i<=m;++i,++j){
if(!nex[j][b[i]]){
puts("NO");
return 0;
}
j=nex[j][b[i]],mark[j]=i;
// printf("mark[%d]=%d\n",j,i);
}
for(int i=m,j=n;i>=1;--i,--j){
if(!pre[j][b[i]]){
puts("NO");
return 0;
}
if(a[j]==b[i])j=pre[j][b[i]^1]+1;
else j=pre[j][b[i]];
// printf("mrk[%d]=%d\n",j,i);
if(mark[j]==i){
puts("YES");
for(int k=1;k<=n;++k)
if(k<=j&&mark[k]||k>j&&mrk[k]){
printf("%d ",k);
}
return 0;
}
mrk[j]=i;
if(i==1&&(pre[j][0]==0||pre[j][1]==0)){
puts("YES");
for(int k=1;k<=n;++k)
if(mrk[k])
printf("%d ",k);
return 0;
}
}
puts("NO");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5808kb
input:
BBAAABBAAABAAA BAAB
output:
NO
result:
wrong answer you didn't find a solution but jury did