QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246004#4669. Genetic Modificationsrqoi031WA 0ms3384kbC++201.8kb2023-11-10 15:17:302023-11-10 15:17:30

Judging History

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

  • [2023-11-10 15:17:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3384kb
  • [2023-11-10 15:17:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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