QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246004 | #4669. Genetic Modifications | rqoi031 | WA | 0ms | 3384kb | C++20 | 1.8kb | 2023-11-10 15:17:30 | 2023-11-10 15:17:30 |
Judging History
answer
#include<stdio.h>
char s[100005],t[100005];
int pre[100005][2];
int nxt[100005][2];
int low[100005];
int upr[100005];
int ans0[100005];
int ans1[100005];
int main()
{
scanf("%s%s",s,t);
const int n(__builtin_strlen(s)),m(__builtin_strlen(t));
pre[0][s[0]^'0']=0;
pre[0][s[0]^'1']=-1;
for(int i=1;i<n;i++)
{
pre[i][s[i]^'0']=i;
pre[i][s[i]^'1']=pre[i-1][s[i]^'1'];
}
pre[n][0]=pre[n-1][0];
pre[n][1]=pre[n-1][1];
nxt[n][0]=n;
nxt[n][1]=n;
for(int i=n-1;i>=0;i--)
{
nxt[i][s[i]^'0']=i;
nxt[i][s[i]^'1']=nxt[i+1][s[i]^'1'];
}
low[0]=0;
for(int i=1;i<n;i++)
{
low[i]=s[i]==s[i-1]?low[i-1]:i;
}
for(int i=n;i>0;i--)
{
low[i]=low[i-1]-1;
}
low[0]=-1;
upr[n]=n-1;
for(int i=n-1;i>=0;i--)
{
upr[i]=s[i]==s[i+1]?upr[i+1]:i;
}
for(int i=0;i<n;i++)
{
upr[i]=upr[i+1]+1;
}
upr[n]=n;
int lt(n),rt(-1);
for(int i=0;i<n;i++)
{
if(s[i]==t[0]&&low[i]==-1)
{
rt=i;
lt=lt<i?lt:i;
}
}
ans0[0]=lt;
for(int i=1;i<m;i++)
{
if(lt>rt)
{
break;
}
lt=nxt[lt+1][t[i]^'0'];
rt=pre[upr[rt]][t[i]^'0'];
rt=rt>=n?n-1:rt;
ans0[i]=lt;
}
if(lt>rt||rt<low[n])
{
puts("NO");
return 0;
}
puts("YES");
ans1[m-1]=rt;
for(int i=m-2;i>=0&&rt>0;i--)
{
rt=low[rt];
rt=nxt[rt<0?0:rt][t[i]^'0'];
ans1[i]=rt;
}
int i(0);
for(;i<m&&ans0[i]>=ans1[i];i++)
{
printf("%d ",ans0[i]+1);
}
for(;i<m;i++)
{
printf("%d ",ans1[i]+1);
}
printf("\n");
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3384kb
input:
BBAAABBAAABAAA BAAB
output:
NO
result:
wrong answer you didn't find a solution but jury did