QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246030 | #4669. Genetic Modifications | Judgelight | WA | 0ms | 20052kb | C++14 | 2.3kb | 2023-11-10 15:36:55 | 2023-11-10 15:36:57 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 100009
using namespace std;
int n,m,_0[N],_1[N];char s[N],t[N];
namespace solve1{
int f[2009][2009],ans[2009],lst[2009];
int mian(){
memset(lst,-1,sizeof(lst));memset(f,-1,sizeof(f));
f[0][0]=0,lst[0]=0;
for(int i=1;i<=n;i++){
int l=min(_0[i-1],_1[i-1]);
for(int j=m;j;j--){
if(s[i]!=t[j])continue;
if(lst[j-1]>=l)f[i][j]=lst[j-1],lst[j]=i;
}
}
for(int i=min(_0[n],_1[n]);i<=n;i++){
if(~f[i][m]){
printf("YES\n");
for(int j=m;j>=1;j--){
ans[j]=i,i=f[i][j];
}
for(int j=1;j<=m;j++)printf("%d ",ans[j]);
return 0;
}
}
printf("NO");
return 0;
}
}
namespace solve2{
int f[N][23],ans[N],lst[N];
int mian(){
memset(lst,-1,sizeof(lst));memset(f,-1,sizeof(f));
f[0][0]=0,lst[0]=0;
for(int i=1;i<=n;i++){
int l=min(_0[i-1],_1[i-1]);
for(int j=m;j;j--){
if(s[i]!=t[j])continue;
if(lst[j-1]>=l)f[i][j]=lst[j-1],lst[j]=i;
}
}
for(int i=min(_0[n],_1[n]);i<=n;i++){
if(~f[i][m]){
printf("YES\n");
for(int j=m;j>=1;j--){
ans[j]=i,i=f[i][j];
}
for(int j=1;j<=m;j++)printf("%d ",ans[j]);
return 0;
}
}
printf("NO");
return 0;
}
}
namespace solve3{
vector<pair<int,int> >v;int p[N];
int mian(){
v.eb(mk(1,1));
for(int i=2;i<=n;i++)if(s[i]==s[i-1])v.back().second=i;else v.eb(mk(i,i));
int j=0;
if(s[v[j].first]!=t[1])j++;
if(j>=v.size()){printf("NO");return 0;}
!j?p[1]=v[j].second:p[1]=v[j].first;
for(int i=2;i<=m;i++){
j++;if(j>=v.size()){printf("NO");return 0;}
p[i-1]==v[j-1].second?p[i]=v[j].second:p[i]=v[j].first;
}
bool vis[2];vis[0]=vis[1]=0;
for(int i=p[m]+1;i<=n;i++)vis[s[i]-'0']=1;
if(vis[0]&&vis[1]){printf("NO");return 0;}
printf("YES\n");
for(int i=1;i<=m;i++)printf("%d ",p[i]);
return 0;
}
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
scanf("%s",t+1),m=strlen(t+1);
for(int i=1;i<=n;i++){
_0[i]=_0[i-1],_1[i]=_1[i-1];
s[i]=='0'?_0[i]=i:_1[i]=i;
}
bool flag=1;
for(int i=2;i<=m;i++)if(t[i]==t[i-1]){flag=0;break;}
if(!flag){if(n<=2000)solve1::mian();else if(m<=20)solve2::mian();else printf("NO");}
else solve3::mian();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 20052kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 4 5 6
result:
wrong answer wrong solution [2]