QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246109 | #4669. Genetic Modifications | Sham_Devour | WA | 1ms | 5872kb | C++14 | 2.3kb | 2023-11-10 16:15:51 | 2023-11-10 16:15:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=1e5+5;
bool f[N][N],F[M][25];
int sum[M];
char a[M],b[M];
int n,m,la[M],s=1,fl;
vector<int> vec;
void solve1() {
for(int i=1;i<=n;i++) {
la[i]=s;
if(a[i]!=a[i+1]) s=i+1;
}
f[0][0]=1;
for(int i=0;i<=n;i++) sum[i+1]=sum[i]+f[i][0];
for(int j=1;j<=m;j++) {
for(int i=1;i<=n;i++) {
if(a[i]==b[j]) {
if(i==la[i]) f[i][j]=(sum[i]-sum[la[i-1]-1])?1:0;
else f[i][j]=(sum[i]-sum[la[i]-1])?1:0;
}
}
for(int i=0;i<=n;i++) sum[i+1]=sum[i]+f[i][j];
}
for(int i=n;i>=1;i--) {
if(f[i][m]) {
int pos=i,w=m;
while(w>0) {
vec.push_back(pos);
int L=(pos==la[pos])?(la[pos-1]-1):(la[pos]-1);
for(int j=pos-1;j>=L;j--)
if(f[j][w-1]) {
pos=j;
w--;
break;
}
}
puts("YES");
for(int j=vec.size()-1;j>=0;j--) printf("%d ",vec[j]);
fl=1;
break;
}
if(i<n&&a[i]!=a[i+1]) break;
}
if(!fl) puts("NO");
}
void solve2() {
for(int i=1;i<=n;i++) {
la[i]=s;
if(a[i]!=a[i+1]) s=i+1;
}
F[0][0]=1;
for(int i=0;i<=n;i++) sum[i+1]=sum[i]+F[i][0];
for(int j=1;j<=m;j++) {
for(int i=1;i<=n;i++) {
if(a[i]==b[j]) {
if(i==la[i]) F[i][j]=(sum[i]-sum[la[i-1]-1])?1:0;
else F[i][j]=(sum[i]-sum[la[i]-1])?1:0;
}
}
for(int i=0;i<=n;i++) sum[i+1]=sum[i]+F[i][j];
}
for(int i=n;i>=1;i--) {
if(F[i][m]) {
int pos=i,w=m;
while(w>0) {
vec.push_back(pos);
int L=(pos==la[pos])?(la[pos-1]-1):(la[pos]-1);
for(int j=pos-1;j>=L;j--)
if(F[j][w-1]) {
pos=j;
w--;
break;
}
}
puts("YES");
for(int j=vec.size()-1;j>=0;j--) printf("%d ",vec[j]);
fl=1;
break;
}
if(i<n&&a[i]!=a[i+1]) break;
}
if(!fl) puts("NO");
}
void solve3() {
a[0]=a[1];a[n+1]=a[n];int T=1,tt=0;
for(int i=1;i<=n;i++)
if(a[i]!=a[i+1]||a[i]!=a[i-1]) {
if(T<=m&&a[i]==b[T]) {
vec.push_back(i);
T++;tt=0;
} else {
tt++;
if(tt>=2) {
puts("NO");
fl=1;
break;
}
}
}
if(!fl) {
if(T>m) {
puts("YES");
for(int j=0;j<vec.size();j++) printf("%d ",vec[j]);
} else puts("NO");
}
}
int main() {
scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);
if(n<=2000&&m<=2000) solve1();
else if(m<=20) solve2();
else solve3();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5872kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5720kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
NO
result:
wrong answer you didn't find a solution but jury did