#include <iostream>
#include <bits/stdc++.h>
#include "dna.h";
typedef long long ll;
using namespace std;
const int mxN=1e5+5;
int d[100005];
int numbersA[mxN][3], numbersB[mxN][3];
int n,q,x,y;
string f,s;
int aa=0, ta=0, ca=0,ab=0, tb=0, cb=0, difference=0;
int rat=0, rta=0, rac=0,rca=0, rtc=0, rct=0;
vector<pair<int,int>>replaceA (mxN,{0,0});
vector<pair<int,int>>replaceT (mxN,{0,0});
vector<pair<int,int>>replaceC (mxN,{0,0});
void init(string a, string b)
{
for(int i=0; i<a.size(); i++)
{
if(a[i]!=b[i])
{
difference++;
}
d[i]=difference;
if(a[i]=='A')
{
aa++;
if(b[i]=='T') rat++;
if(b[i]=='C') rac++;
}
else if (a[i]=='T')
{
ta++;
if(b[i]=='A') rta++;
if(b[i]=='C') rtc++;
}
else if (a[i]=='C')
{
ca++;
if(b[i]=='A') rca++;
if(b[i]=='T') rct++;
}
numbersA[i][0]=aa;
numbersA[i][1]=ta;
numbersA[i][2]=ca;
replaceA[i].first=rat;
replaceA[i].second=rac;
replaceT[i].first=rta;
replaceT[i].second=rtc;
replaceC[i].first=rca;
replaceC[i].second=rct;
if(b[i]=='A')
{
ab++;
}
else if (b[i]=='T')
{
tb++;
}
else if (b[i]=='C')
{
cb++;
}
numbersB[i][0]=ab;
numbersB[i][1]=tb;
numbersB[i][2]=cb;
}
}
int get_distance(int x,int y)
{
int ans=0;
int div=d[y];
int da1=numbersA[y][0], dt1=numbersA[y][1], dc1=numbersA[y][2], da2=numbersB[y][0], dt2=numbersB[y][1], dc2=numbersB[y][2] ;
int rati=replaceA[y].first, rtai=replaceT[y].first, raci=replaceA[y].second, rcai=replaceC[y].first, rtci=replaceT[y].second, rcti=replaceC[y].second;
if(x!=0)
{
div-=d[x-1];
da1-=numbersA[x-1][0];
dt1-=numbersA[x-1][1];
dc1-=numbersA[x-1][2];
da2-=numbersB[x-1][0];
dt2-=numbersB[x-1][1];
dc2-=numbersB[x-1][2];
rati-=replaceA[x].first;
rtai-=replaceT[x].first;
raci-=replaceA[x].second;
rcai-=replaceC[x].first;
rtci-=replaceT[x].second;
rcti-=replaceC[x].second;
}
if(da1==da2 && dt1==dt2 && dc1==dc2)
{
ans+=min(rati,rtai);
div-=(min(rati,rtai))*2;
ans+=min(raci,rcai);
div-=(min(raci,rcai))*2;
ans+=min(rtci,rcti);
div-=(min(rtci,rcti))*2;
if(div>1)
{
ans+=(div*2)/3;
}
return ans;
}
else
{
return -1;
}
}
Compilation message
dna.cpp:3:17: warning: extra tokens at end of #include directive
3 | #include "dna.h";
| ^
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0; i<a.size(); i++)
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
8540 KB |
Output is correct |
2 |
Correct |
34 ms |
8524 KB |
Output is correct |
3 |
Correct |
34 ms |
8208 KB |
Output is correct |
4 |
Correct |
35 ms |
8624 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
5 ms |
6100 KB |
Output is correct |
5 |
Correct |
5 ms |
6180 KB |
Output is correct |
6 |
Correct |
6 ms |
6144 KB |
Output is correct |
7 |
Correct |
5 ms |
5912 KB |
Output is correct |
8 |
Correct |
5 ms |
6148 KB |
Output is correct |
9 |
Correct |
4 ms |
6144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
5 ms |
6100 KB |
Output is correct |
5 |
Correct |
5 ms |
6180 KB |
Output is correct |
6 |
Correct |
6 ms |
6144 KB |
Output is correct |
7 |
Correct |
5 ms |
5912 KB |
Output is correct |
8 |
Correct |
5 ms |
6148 KB |
Output is correct |
9 |
Correct |
4 ms |
6144 KB |
Output is correct |
10 |
Correct |
37 ms |
8488 KB |
Output is correct |
11 |
Correct |
36 ms |
8600 KB |
Output is correct |
12 |
Correct |
35 ms |
8732 KB |
Output is correct |
13 |
Correct |
34 ms |
8740 KB |
Output is correct |
14 |
Correct |
38 ms |
8876 KB |
Output is correct |
15 |
Correct |
33 ms |
8840 KB |
Output is correct |
16 |
Correct |
33 ms |
8600 KB |
Output is correct |
17 |
Correct |
34 ms |
8744 KB |
Output is correct |
18 |
Correct |
33 ms |
8876 KB |
Output is correct |
19 |
Correct |
30 ms |
8660 KB |
Output is correct |
20 |
Correct |
33 ms |
8748 KB |
Output is correct |
21 |
Correct |
31 ms |
8840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
5 ms |
6100 KB |
Output is correct |
5 |
Correct |
5 ms |
6180 KB |
Output is correct |
6 |
Correct |
6 ms |
6144 KB |
Output is correct |
7 |
Correct |
5 ms |
5912 KB |
Output is correct |
8 |
Correct |
5 ms |
6148 KB |
Output is correct |
9 |
Correct |
4 ms |
6144 KB |
Output is correct |
10 |
Correct |
5 ms |
5844 KB |
Output is correct |
11 |
Correct |
6 ms |
6148 KB |
Output is correct |
12 |
Correct |
6 ms |
5892 KB |
Output is correct |
13 |
Correct |
6 ms |
6116 KB |
Output is correct |
14 |
Correct |
6 ms |
6176 KB |
Output is correct |
15 |
Correct |
4 ms |
6100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
8540 KB |
Output is correct |
2 |
Correct |
34 ms |
8524 KB |
Output is correct |
3 |
Correct |
34 ms |
8208 KB |
Output is correct |
4 |
Correct |
35 ms |
8624 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2680 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
5 ms |
6100 KB |
Output is correct |
12 |
Correct |
5 ms |
6180 KB |
Output is correct |
13 |
Correct |
6 ms |
6144 KB |
Output is correct |
14 |
Correct |
5 ms |
5912 KB |
Output is correct |
15 |
Correct |
5 ms |
6148 KB |
Output is correct |
16 |
Correct |
4 ms |
6144 KB |
Output is correct |
17 |
Correct |
37 ms |
8488 KB |
Output is correct |
18 |
Correct |
36 ms |
8600 KB |
Output is correct |
19 |
Correct |
35 ms |
8732 KB |
Output is correct |
20 |
Correct |
34 ms |
8740 KB |
Output is correct |
21 |
Correct |
38 ms |
8876 KB |
Output is correct |
22 |
Correct |
33 ms |
8840 KB |
Output is correct |
23 |
Correct |
33 ms |
8600 KB |
Output is correct |
24 |
Correct |
34 ms |
8744 KB |
Output is correct |
25 |
Correct |
33 ms |
8876 KB |
Output is correct |
26 |
Correct |
30 ms |
8660 KB |
Output is correct |
27 |
Correct |
33 ms |
8748 KB |
Output is correct |
28 |
Correct |
31 ms |
8840 KB |
Output is correct |
29 |
Correct |
5 ms |
5844 KB |
Output is correct |
30 |
Correct |
6 ms |
6148 KB |
Output is correct |
31 |
Correct |
6 ms |
5892 KB |
Output is correct |
32 |
Correct |
6 ms |
6116 KB |
Output is correct |
33 |
Correct |
6 ms |
6176 KB |
Output is correct |
34 |
Correct |
4 ms |
6100 KB |
Output is correct |
35 |
Correct |
1 ms |
2644 KB |
Output is correct |
36 |
Correct |
36 ms |
8260 KB |
Output is correct |
37 |
Correct |
35 ms |
8608 KB |
Output is correct |
38 |
Correct |
36 ms |
8796 KB |
Output is correct |
39 |
Correct |
36 ms |
8924 KB |
Output is correct |
40 |
Correct |
35 ms |
8968 KB |
Output is correct |
41 |
Correct |
4 ms |
6100 KB |
Output is correct |
42 |
Correct |
33 ms |
8708 KB |
Output is correct |
43 |
Correct |
32 ms |
8872 KB |
Output is correct |
44 |
Correct |
33 ms |
8880 KB |
Output is correct |
45 |
Correct |
32 ms |
8724 KB |
Output is correct |
46 |
Correct |
35 ms |
8968 KB |
Output is correct |
47 |
Correct |
31 ms |
8900 KB |
Output is correct |