#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e9;
const int MAX_N=1e5+10;
int na[MAX_N][4],nb[MAX_N][4];
int gda[MAX_N][4],gdc[MAX_N][4],gdt[MAX_N][4];
int dif[MAX_N];
vector<int> da(3),dc(3),dt(3);
int n;
void init(std::string a, std::string b) {
memset(na,0,sizeof na);
memset(nb,0,sizeof nb);
memset(gda,0,sizeof gda); memset(gdc,0,sizeof gdc); memset(gdt,0,sizeof gdt);
memset(dif,0,sizeof dif);
n=a.size();
for(int i=0;i<n;i++){
if(i!=0){
for(int j=0;j<3;j++) na[i][j]=na[i-1][j];
for(int j=0;j<3;j++) nb[i][j]=nb[i-1][j];
}
if(a[i]=='A') na[i][0]++;
if(a[i]=='C') na[i][1]++;
if(a[i]=='T') na[i][2]++;
if(b[i]=='A') nb[i][0]++;
if(b[i]=='C') nb[i][1]++;
if(b[i]=='T') nb[i][2]++;
}
for(int i=0;i<n;i++){
if(i!=0){
dif[i]=dif[i-1];
for(int j=0;j<3;j++) gda[i][j]=gda[i-1][j];
for(int j=0;j<3;j++) gdc[i][j]=gdc[i-1][j];
for(int j=0;j<3;j++) gdt[i][j]=gdt[i-1][j];
}
if(a[i]!=b[i]) dif[i]++;
int id=0;
if(a[i]=='A') id=0;
if(a[i]=='C') id=1;
if(a[i]=='T') id=2;
if(b[i]=='A') gda[i][id]++;
if(b[i]=='C') gdc[i][id]++;
if(b[i]=='T') gdt[i][id]++;
}
}
int get_distance(int x, int y) {
int aa,ac,at,ba,bc,bt,c;
if(x==0){
aa=na[y][0]; ac=na[y][1]; at=na[y][2];
ba=nb[y][0]; bc=nb[y][1]; bt=nb[y][2];
da[0]=gda[y][0]; da[1]=gda[y][1]; da[2]=gda[y][2];
dc[0]=gdc[y][0]; dc[1]=gdc[y][1]; dc[2]=gdc[y][2];
dt[0]=gdt[y][0]; dt[1]=gdt[y][1]; dt[2]=gdt[y][2];
c=dif[y];
}
else{
aa=na[y][0]-na[x-1][0]; ac=na[y][1]-na[x-1][1]; at=na[y][2]-na[x-1][2];
ba=nb[y][0]-nb[x-1][0]; bc=nb[y][1]-nb[x-1][1]; bt=nb[y][2]-nb[x-1][2];
da[0]=gda[y][0]-gda[x-1][0]; da[1]=gda[y][1]-gda[x-1][1]; da[2]=gda[y][2]-gda[x-1][2];
dc[0]=gdc[y][0]-gdc[x-1][0]; dc[1]=gdc[y][1]-gdc[x-1][1]; dc[2]=gdc[y][2]-gdc[x-1][2];
dt[0]=gdt[y][0]-gdt[x-1][0]; dt[1]=gdt[y][1]-gdt[x-1][1]; dt[2]=gdt[y][2]-gdt[x-1][2];
c=dif[y]-dif[x-1];
}
if(aa!=ba || ac!=bc || at!=bt) return -1;
int res=MAX;
int rp,d=(y-x)+1;
rp=0;
for(int i=0;i<3;i++){
if(dc[i]==0) continue;
int mi;
if(i==0){
mi=min(dc[i],da[1]);
dc[i]-=mi; da[1]-=mi;
rp+=mi; c-=mi*2;
}
if(i==2){
mi=min(dc[i],dt[1]);
dc[i]-=mi; dt[1]-=mi;
rp+=mi; c-=mi*2;
}
}
for(int i=0;i<3;i++){
if(dc[i]==0) continue;
if(i==0){
rp+=dc[i]; c-=dc[i];
dt[0]+=dc[i];
dc[i]=0;
}
if(i==2){
rp+=dc[i]; c-=dc[i];
da[2]+=dc[i];
dc[i]=0;
}
}
rp+=c/2;
return rp;
}
Compilation message
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:69:7: warning: unused variable 'res' [-Wunused-variable]
69 | int res=MAX;
| ^~~
dna.cpp:70:10: warning: unused variable 'd' [-Wunused-variable]
70 | int rp,d=(y-x)+1;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
10364 KB |
Output is correct |
2 |
Correct |
59 ms |
10328 KB |
Output is correct |
3 |
Correct |
54 ms |
10344 KB |
Output is correct |
4 |
Correct |
56 ms |
10372 KB |
Output is correct |
5 |
Correct |
5 ms |
8396 KB |
Output is correct |
6 |
Correct |
5 ms |
8396 KB |
Output is correct |
7 |
Correct |
5 ms |
8396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8396 KB |
Output is correct |
2 |
Correct |
5 ms |
8444 KB |
Output is correct |
3 |
Correct |
5 ms |
8396 KB |
Output is correct |
4 |
Correct |
9 ms |
9036 KB |
Output is correct |
5 |
Correct |
9 ms |
9096 KB |
Output is correct |
6 |
Correct |
9 ms |
9036 KB |
Output is correct |
7 |
Correct |
9 ms |
9036 KB |
Output is correct |
8 |
Correct |
10 ms |
9036 KB |
Output is correct |
9 |
Correct |
8 ms |
9036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8396 KB |
Output is correct |
2 |
Correct |
5 ms |
8444 KB |
Output is correct |
3 |
Correct |
5 ms |
8396 KB |
Output is correct |
4 |
Correct |
9 ms |
9036 KB |
Output is correct |
5 |
Correct |
9 ms |
9096 KB |
Output is correct |
6 |
Correct |
9 ms |
9036 KB |
Output is correct |
7 |
Correct |
9 ms |
9036 KB |
Output is correct |
8 |
Correct |
10 ms |
9036 KB |
Output is correct |
9 |
Correct |
8 ms |
9036 KB |
Output is correct |
10 |
Correct |
56 ms |
10368 KB |
Output is correct |
11 |
Correct |
60 ms |
10372 KB |
Output is correct |
12 |
Correct |
56 ms |
10636 KB |
Output is correct |
13 |
Correct |
59 ms |
12020 KB |
Output is correct |
14 |
Correct |
64 ms |
12056 KB |
Output is correct |
15 |
Correct |
57 ms |
12020 KB |
Output is correct |
16 |
Correct |
53 ms |
11920 KB |
Output is correct |
17 |
Correct |
49 ms |
11888 KB |
Output is correct |
18 |
Correct |
52 ms |
11904 KB |
Output is correct |
19 |
Correct |
44 ms |
11952 KB |
Output is correct |
20 |
Correct |
42 ms |
11876 KB |
Output is correct |
21 |
Correct |
42 ms |
12032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8396 KB |
Output is correct |
2 |
Correct |
5 ms |
8444 KB |
Output is correct |
3 |
Correct |
5 ms |
8396 KB |
Output is correct |
4 |
Correct |
9 ms |
9036 KB |
Output is correct |
5 |
Correct |
9 ms |
9096 KB |
Output is correct |
6 |
Correct |
9 ms |
9036 KB |
Output is correct |
7 |
Correct |
9 ms |
9036 KB |
Output is correct |
8 |
Correct |
10 ms |
9036 KB |
Output is correct |
9 |
Correct |
8 ms |
9036 KB |
Output is correct |
10 |
Correct |
10 ms |
9036 KB |
Output is correct |
11 |
Correct |
10 ms |
9036 KB |
Output is correct |
12 |
Correct |
10 ms |
9036 KB |
Output is correct |
13 |
Correct |
10 ms |
9036 KB |
Output is correct |
14 |
Correct |
10 ms |
9036 KB |
Output is correct |
15 |
Correct |
8 ms |
9096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
10364 KB |
Output is correct |
2 |
Correct |
59 ms |
10328 KB |
Output is correct |
3 |
Correct |
54 ms |
10344 KB |
Output is correct |
4 |
Correct |
56 ms |
10372 KB |
Output is correct |
5 |
Correct |
5 ms |
8396 KB |
Output is correct |
6 |
Correct |
5 ms |
8396 KB |
Output is correct |
7 |
Correct |
5 ms |
8396 KB |
Output is correct |
8 |
Correct |
5 ms |
8396 KB |
Output is correct |
9 |
Correct |
5 ms |
8444 KB |
Output is correct |
10 |
Correct |
5 ms |
8396 KB |
Output is correct |
11 |
Correct |
9 ms |
9036 KB |
Output is correct |
12 |
Correct |
9 ms |
9096 KB |
Output is correct |
13 |
Correct |
9 ms |
9036 KB |
Output is correct |
14 |
Correct |
9 ms |
9036 KB |
Output is correct |
15 |
Correct |
10 ms |
9036 KB |
Output is correct |
16 |
Correct |
8 ms |
9036 KB |
Output is correct |
17 |
Correct |
56 ms |
10368 KB |
Output is correct |
18 |
Correct |
60 ms |
10372 KB |
Output is correct |
19 |
Correct |
56 ms |
10636 KB |
Output is correct |
20 |
Correct |
59 ms |
12020 KB |
Output is correct |
21 |
Correct |
64 ms |
12056 KB |
Output is correct |
22 |
Correct |
57 ms |
12020 KB |
Output is correct |
23 |
Correct |
53 ms |
11920 KB |
Output is correct |
24 |
Correct |
49 ms |
11888 KB |
Output is correct |
25 |
Correct |
52 ms |
11904 KB |
Output is correct |
26 |
Correct |
44 ms |
11952 KB |
Output is correct |
27 |
Correct |
42 ms |
11876 KB |
Output is correct |
28 |
Correct |
42 ms |
12032 KB |
Output is correct |
29 |
Correct |
10 ms |
9036 KB |
Output is correct |
30 |
Correct |
10 ms |
9036 KB |
Output is correct |
31 |
Correct |
10 ms |
9036 KB |
Output is correct |
32 |
Correct |
10 ms |
9036 KB |
Output is correct |
33 |
Correct |
10 ms |
9036 KB |
Output is correct |
34 |
Correct |
8 ms |
9096 KB |
Output is correct |
35 |
Correct |
5 ms |
8396 KB |
Output is correct |
36 |
Correct |
56 ms |
11604 KB |
Output is correct |
37 |
Correct |
59 ms |
11688 KB |
Output is correct |
38 |
Correct |
59 ms |
12028 KB |
Output is correct |
39 |
Correct |
60 ms |
12032 KB |
Output is correct |
40 |
Correct |
64 ms |
12032 KB |
Output is correct |
41 |
Correct |
9 ms |
9292 KB |
Output is correct |
42 |
Correct |
55 ms |
11876 KB |
Output is correct |
43 |
Correct |
56 ms |
12032 KB |
Output is correct |
44 |
Correct |
58 ms |
12008 KB |
Output is correct |
45 |
Correct |
42 ms |
11952 KB |
Output is correct |
46 |
Correct |
43 ms |
12032 KB |
Output is correct |
47 |
Correct |
45 ms |
12012 KB |
Output is correct |