QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246321 | #4669. Genetic Modifications | Judgelight | WA | 1ms | 4264kb | C++14 | 1.1kb | 2023-11-10 19:00:13 | 2023-11-10 19:00:17 |
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,f[N],g[N],sum[N][2];char s[N],t[N];
bool check(int l,int r){if(l>r)return 1;return !(sum[r][0]-sum[l-1][0])||!(sum[r][1]-sum[l-1][1]);}
signed main(){
//freopen("sequence4.in","r",stdin);
scanf("%s",s+1),n=strlen(s+1);scanf("%s",t+1),m=strlen(t+1);
for(int i=1;i<=n;i++)s[i]=s[i]-'A'+'0';
for(int i=1;i<=m;i++)t[i]=t[i]-'A'+'0';
for(int i=1;i<=n;i++)sum[i][0]=sum[i-1][0]+(s[i]=='0'),sum[i][1]=sum[i-1][1]+(s[i]=='1');
for(int i=1;i<=m;i++){
f[i]=f[i-1]+1;
while(f[i]<=n&&s[f[i]]!=t[i])f[i]++;
}
if(f[m]>n){printf("NO");return 0;}
g[m+1]=n+1;
for(int i=m;i>=1;i--){
g[i]=g[i+1]-1;
while(g[i]>=1&&s[g[i]]!=t[i])g[i]--;
while(g[i]>1&&s[g[i]-1]==t[i]&&check(g[i],g[i+1]-1))g[i]--;
}
for(int i=0;i<=m;i++){
if(f[i]>g[i+1])continue;
if(check(f[i]+1,g[i+1]-1)){
printf("YES\n");
for(int j=1;j<=i;j++)printf("%d ",f[j]);
for(int j=i+1;j<=m;j++)printf("%d ",g[j]);
return 0;
}
}
printf("NO");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 4264kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 4116kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
YES 1 2 4 5 6 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 63 64 66 67 69 70 71 72 73 74 75 76 77 78 79 80 81 83 85 86 87 88 89 90 91 92 95 96 97 98 99 100 101 102 104 105 106 107 108 109 110 11...
result:
wrong answer you selected 13055 multiple times