#include <bits/stdc++.h>
#include "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
using namespace std;
vector <int> poza[5],pozb[5];
int n,sum[100005],val[505];
int caterinca[100005][4][4];
void init (string a,string b)
{
n=a.size();
val['A']=1;
val['T']=2;
val['C']=3;
for (int i=0; i<a.size(); i++)
{
if (i==0)
{
sum[i]=(a[i]!=b[i]);
}
else
{
sum[i]=sum[i-1]+(a[i]!=b[i]);
}
if (i>0)
{
for (int t=1; t<=3; t++)
{
for (int k=1; k<=3; k++)
{
caterinca[i][t][k]=caterinca[i-1][t][k];
}
}
}
caterinca[i][val[a[i]]][val[b[i]]]++;
poza[val[a[i]]].push_back(i);
pozb[val[b[i]]].push_back(i);
}
}
int cautsta(int loc,int poz)
{
int st=0,dr=(int)poza[loc].size()-1,mij;
int sol=poza[loc].size();
while (st<=dr)
{
mij=(st+dr)/2;
if (poza[loc][mij]>=poz)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return sol;
}
int cautstb(int loc,int poz)
{
int st=0,dr=(int)pozb[loc].size()-1,mij;
int sol=pozb[loc].size();
while (st<=dr)
{
mij=(st+dr)/2;
if (pozb[loc][mij]>=poz)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return sol;
}
int cautdra(int loc,int poz)
{
int st=0,dr=(int)poza[loc].size()-1,mij;
int sol=-1;
while (st<=dr)
{
mij=(st+dr)/2;
if (poza[loc][mij]<=poz)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return sol;
}
int cautdrb(int loc,int poz)
{
int st=0,dr=(int)pozb[loc].size()-1,mij;
int sol=-1;
while (st<=dr)
{
mij=(st+dr)/2;
if (pozb[loc][mij]<=poz)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return sol;
}
int get_distance(int x,int y)
{
for (int i=1; i<=3; i++)
{
int sta,stb,dra,drb;
sta=cautsta(i,x);
stb=cautstb(i,x);
dra=cautdra(i,y);
drb=cautdrb(i,y);
if (dra-sta!=drb-stb)
{
return -1;
}
}
int bonjour[4][4],sum=0,i,j;
for (i=1; i<=3; i++)
{
for (j=1; j<=3; j++)
{
if (i!=j)
{
if (x==0)
{
bonjour[i][j]=caterinca[y][i][j];
bonjour[j][i]=caterinca[y][j][i];
}
else
{
bonjour[i][j]=caterinca[y][i][j]-caterinca[x-1][i][j];
bonjour[j][i]=caterinca[y][j][i]-caterinca[x-1][j][i];
}
}
}
}
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (i!=j)
{
int val=min(bonjour[i][j],bonjour[j][i]);
sum=sum+val;
bonjour[i][j]-=val;
bonjour[j][i]-=val;
}
}
}
int ok=0,sum2=0;
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (i!=j&&bonjour[i][j]!=0)
{
sum2=sum2+bonjour[i][j];
}
}
}
sum=sum+2*sum2/3;
return sum;
}
/*int main() {
int n, q;
assert(scanf("%d %d", &n, &q) == 2);
char A[n+1], B[n+1];
assert(scanf("%s", A) == 1);
assert(scanf("%s", B) == 1);
std::string a = std::string(A);
std::string b = std::string(B);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}*/
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i=0; i<a.size(); i++)
| ~^~~~~~~~~
dna.cpp:37:30: warning: array subscript has type 'char' [-Wchar-subscripts]
37 | caterinca[i][val[a[i]]][val[b[i]]]++;
| ^
dna.cpp:37:41: warning: array subscript has type 'char' [-Wchar-subscripts]
37 | caterinca[i][val[a[i]]][val[b[i]]]++;
| ^
dna.cpp:38:22: warning: array subscript has type 'char' [-Wchar-subscripts]
38 | poza[val[a[i]]].push_back(i);
| ^
dna.cpp:39:22: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | pozb[val[b[i]]].push_back(i);
| ^
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:165:9: warning: unused variable 'ok' [-Wunused-variable]
165 | int ok=0,sum2=0;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
154 ms |
9660 KB |
Output is correct |
2 |
Correct |
148 ms |
9684 KB |
Output is correct |
3 |
Correct |
180 ms |
9116 KB |
Output is correct |
4 |
Correct |
204 ms |
9916 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
8264 KB |
Output is correct |
5 |
Correct |
9 ms |
8520 KB |
Output is correct |
6 |
Correct |
9 ms |
8324 KB |
Output is correct |
7 |
Correct |
8 ms |
7900 KB |
Output is correct |
8 |
Correct |
11 ms |
8440 KB |
Output is correct |
9 |
Correct |
9 ms |
8368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
8264 KB |
Output is correct |
5 |
Correct |
9 ms |
8520 KB |
Output is correct |
6 |
Correct |
9 ms |
8324 KB |
Output is correct |
7 |
Correct |
8 ms |
7900 KB |
Output is correct |
8 |
Correct |
11 ms |
8440 KB |
Output is correct |
9 |
Correct |
9 ms |
8368 KB |
Output is correct |
10 |
Correct |
142 ms |
9696 KB |
Output is correct |
11 |
Correct |
147 ms |
9684 KB |
Output is correct |
12 |
Correct |
155 ms |
9672 KB |
Output is correct |
13 |
Correct |
171 ms |
9784 KB |
Output is correct |
14 |
Correct |
152 ms |
10112 KB |
Output is correct |
15 |
Correct |
152 ms |
10024 KB |
Output is correct |
16 |
Correct |
139 ms |
9712 KB |
Output is correct |
17 |
Correct |
134 ms |
9788 KB |
Output is correct |
18 |
Correct |
135 ms |
10140 KB |
Output is correct |
19 |
Correct |
110 ms |
9540 KB |
Output is correct |
20 |
Correct |
112 ms |
9708 KB |
Output is correct |
21 |
Correct |
106 ms |
10196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
8264 KB |
Output is correct |
5 |
Correct |
9 ms |
8520 KB |
Output is correct |
6 |
Correct |
9 ms |
8324 KB |
Output is correct |
7 |
Correct |
8 ms |
7900 KB |
Output is correct |
8 |
Correct |
11 ms |
8440 KB |
Output is correct |
9 |
Correct |
9 ms |
8368 KB |
Output is correct |
10 |
Correct |
10 ms |
7860 KB |
Output is correct |
11 |
Correct |
10 ms |
8556 KB |
Output is correct |
12 |
Correct |
9 ms |
8012 KB |
Output is correct |
13 |
Correct |
10 ms |
8900 KB |
Output is correct |
14 |
Correct |
12 ms |
8760 KB |
Output is correct |
15 |
Correct |
11 ms |
8748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
154 ms |
9660 KB |
Output is correct |
2 |
Correct |
148 ms |
9684 KB |
Output is correct |
3 |
Correct |
180 ms |
9116 KB |
Output is correct |
4 |
Correct |
204 ms |
9916 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
9 ms |
8264 KB |
Output is correct |
12 |
Correct |
9 ms |
8520 KB |
Output is correct |
13 |
Correct |
9 ms |
8324 KB |
Output is correct |
14 |
Correct |
8 ms |
7900 KB |
Output is correct |
15 |
Correct |
11 ms |
8440 KB |
Output is correct |
16 |
Correct |
9 ms |
8368 KB |
Output is correct |
17 |
Correct |
142 ms |
9696 KB |
Output is correct |
18 |
Correct |
147 ms |
9684 KB |
Output is correct |
19 |
Correct |
155 ms |
9672 KB |
Output is correct |
20 |
Correct |
171 ms |
9784 KB |
Output is correct |
21 |
Correct |
152 ms |
10112 KB |
Output is correct |
22 |
Correct |
152 ms |
10024 KB |
Output is correct |
23 |
Correct |
139 ms |
9712 KB |
Output is correct |
24 |
Correct |
134 ms |
9788 KB |
Output is correct |
25 |
Correct |
135 ms |
10140 KB |
Output is correct |
26 |
Correct |
110 ms |
9540 KB |
Output is correct |
27 |
Correct |
112 ms |
9708 KB |
Output is correct |
28 |
Correct |
106 ms |
10196 KB |
Output is correct |
29 |
Correct |
10 ms |
7860 KB |
Output is correct |
30 |
Correct |
10 ms |
8556 KB |
Output is correct |
31 |
Correct |
9 ms |
8012 KB |
Output is correct |
32 |
Correct |
10 ms |
8900 KB |
Output is correct |
33 |
Correct |
12 ms |
8760 KB |
Output is correct |
34 |
Correct |
11 ms |
8748 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
176 ms |
10444 KB |
Output is correct |
37 |
Correct |
189 ms |
11276 KB |
Output is correct |
38 |
Correct |
207 ms |
11064 KB |
Output is correct |
39 |
Correct |
205 ms |
11600 KB |
Output is correct |
40 |
Correct |
188 ms |
11728 KB |
Output is correct |
41 |
Correct |
9 ms |
8628 KB |
Output is correct |
42 |
Correct |
164 ms |
10956 KB |
Output is correct |
43 |
Correct |
188 ms |
11528 KB |
Output is correct |
44 |
Correct |
169 ms |
11624 KB |
Output is correct |
45 |
Correct |
139 ms |
10876 KB |
Output is correct |
46 |
Correct |
139 ms |
11640 KB |
Output is correct |
47 |
Correct |
139 ms |
11380 KB |
Output is correct |