QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246241 | #4669. Genetic Modifications | Sham_Devour | RE | 0ms | 3784kb | C++14 | 927b | 2023-11-10 17:43:47 | 2023-11-10 17:43:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N],t[N];
int n,m,A,B;
int L[N],R[N];
vector<int> Lv,Rv,vec;
int main() {
scanf("%s%s",s+1,t+1);s[0]=s[1],s[n+1]=s[n];
n=strlen(s+1);m=strlen(t+1);
for(int i=1;i<=n;i++) {
L[i]=L[i-1];
if(L[i]==m&&s[i]!=s[i+1]) L[i]=-1;
if(t[L[i]+1]==s[i]) {
L[i]++;
Lv.push_back(i);
}
}
for(int i=n;i>=1;i--) {
R[i]=R[i+1];
if(R[i]==m&&s[i]!=s[i-1]) R[i]=-1;
if(s[i]!=s[i-1]&&s[i]==t[m-R[i]]) {
R[i]++;
Rv.push_back(i);
} else if(s[i]!=s[i+1]&&t[m-R[i]]==s[i]&&Rv.back()!=i+1) {
R[i]++;
Rv.push_back(i);
}
}
for(int i=0;i<n;i++)
if(L[i]!=-1&&R[i+1]!=-1&&L[i]+R[i+1]==m) {
puts("YES");
for(auto x:Lv)
if(x<=i) vec.push_back(x);
for(auto x:Rv)
if(x>i) vec.push_back(x);
sort(vec.begin(),vec.end());
for(auto x:vec) printf("%d ",x);
return 0;
}
puts("NO");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: -100
Runtime Error
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...