# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
877582 |
2023-11-23T10:47:33 Z |
tigar |
Mutating DNA (IOI21_dna) |
C++17 |
|
37 ms |
7560 KB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int ac[100010], ca[100010], ab[100010], ba[100010], bc[100010], cb[100010], aa[100010], bb[100010], cc[100010];
void init(string a, string b)
{
for(int i=0; i<a.size(); i++)
{
ca[i+1]=ca[i]; ac[i+1]=ac[i]; ba[i+1]=ba[i];
ab[i+1]=ab[i]; cb[i+1]=cb[i]; bc[i+1]=bc[i];
aa[i+1]=aa[i]; bb[i+1]=bb[i]; cc[i+1]=cc[i];
if(a[i]=='A' and b[i]=='T')ab[i+1]++;
if(a[i]=='A' and b[i]=='C')ac[i+1]++;
if(a[i]=='T' and b[i]=='C')bc[i+1]++;
if(a[i]=='C' and b[i]=='T')cb[i+1]++;
if(a[i]=='T' and b[i]=='A')ba[i+1]++;
if(a[i]=='C' and b[i]=='A')ca[i+1]++;
if(a[i]=='A' and b[i]=='A')aa[i+1]++;
if(a[i]=='T' and b[i]=='T')bb[i+1]++;
if(a[i]=='C' and b[i]=='C')cc[i+1]++;
}
}
int calc(int *niz, int x, int y)
{
return niz[y]-niz[x-1];
}
int get_distance(int x, int y)
{
x++; y++;
if(calc(ab, x, y)+calc(ac, x, y)!=calc(ba, x, y)+calc(ca, x, y))return -1;
if(calc(ab, x, y)+calc(cb, x, y)!=calc(ba, x, y)+calc(bc, x, y))return -1;
if(calc(bc, x, y)+calc(ac, x, y)!=calc(cb, x, y)+calc(ca, x, y))return -1;
int dist=y-x+1;
dist-=calc(aa, x, y);
dist-=calc(bb, x, y);
dist-=calc(cc, x, y);
int BA=calc(ba, x, y), AB=calc(ab, x, y), BC=calc(bc, x, y), CB=calc(cb, x, y), CA=calc(ca, x, y), AC=calc(ac, x, y);
int cyc1=min(AB, BA);
AB-=cyc1; BA-=cyc1; dist-=cyc1;
int cyc2=min(AC, CA);
AC-=cyc2; CA-=cyc2; dist-=cyc2;
int cyc3=min(BC, CB);
CB-=cyc3; BC-=cyc3; dist-=cyc3;
if(AB!=BC or BC!=CA or CA!=AB)return -1;
else dist-=AB;
if(BA!=AC or AC!=CB or CB!=BA)return -1;
else dist-=BA;
return dist;
}
/*int main()
{
string a, b;
cin>>a>>b;
init(a, b);
int q;cin>>q;
while(q--)
{
int x, y; cin>>x>>y;
cout<<get_distance(x, y)<<endl;
}
}*/
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i=0; i<a.size(); i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5660 KB |
Output is correct |
2 |
Correct |
26 ms |
7128 KB |
Output is correct |
3 |
Correct |
25 ms |
6692 KB |
Output is correct |
4 |
Correct |
25 ms |
7160 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
4668 KB |
Output is correct |
5 |
Correct |
4 ms |
4700 KB |
Output is correct |
6 |
Correct |
4 ms |
4640 KB |
Output is correct |
7 |
Correct |
4 ms |
4320 KB |
Output is correct |
8 |
Correct |
4 ms |
4696 KB |
Output is correct |
9 |
Correct |
3 ms |
4680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
4668 KB |
Output is correct |
5 |
Correct |
4 ms |
4700 KB |
Output is correct |
6 |
Correct |
4 ms |
4640 KB |
Output is correct |
7 |
Correct |
4 ms |
4320 KB |
Output is correct |
8 |
Correct |
4 ms |
4696 KB |
Output is correct |
9 |
Correct |
3 ms |
4680 KB |
Output is correct |
10 |
Correct |
25 ms |
7044 KB |
Output is correct |
11 |
Correct |
32 ms |
7160 KB |
Output is correct |
12 |
Correct |
27 ms |
7452 KB |
Output is correct |
13 |
Correct |
28 ms |
7372 KB |
Output is correct |
14 |
Correct |
26 ms |
7436 KB |
Output is correct |
15 |
Correct |
25 ms |
7464 KB |
Output is correct |
16 |
Correct |
37 ms |
7132 KB |
Output is correct |
17 |
Correct |
28 ms |
7280 KB |
Output is correct |
18 |
Correct |
25 ms |
7308 KB |
Output is correct |
19 |
Correct |
26 ms |
7196 KB |
Output is correct |
20 |
Correct |
24 ms |
7236 KB |
Output is correct |
21 |
Correct |
24 ms |
7436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
4668 KB |
Output is correct |
5 |
Correct |
4 ms |
4700 KB |
Output is correct |
6 |
Correct |
4 ms |
4640 KB |
Output is correct |
7 |
Correct |
4 ms |
4320 KB |
Output is correct |
8 |
Correct |
4 ms |
4696 KB |
Output is correct |
9 |
Correct |
3 ms |
4680 KB |
Output is correct |
10 |
Correct |
5 ms |
4188 KB |
Output is correct |
11 |
Correct |
5 ms |
4700 KB |
Output is correct |
12 |
Correct |
4 ms |
4444 KB |
Output is correct |
13 |
Correct |
4 ms |
4952 KB |
Output is correct |
14 |
Correct |
4 ms |
4696 KB |
Output is correct |
15 |
Correct |
3 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5660 KB |
Output is correct |
2 |
Correct |
26 ms |
7128 KB |
Output is correct |
3 |
Correct |
25 ms |
6692 KB |
Output is correct |
4 |
Correct |
25 ms |
7160 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
4668 KB |
Output is correct |
12 |
Correct |
4 ms |
4700 KB |
Output is correct |
13 |
Correct |
4 ms |
4640 KB |
Output is correct |
14 |
Correct |
4 ms |
4320 KB |
Output is correct |
15 |
Correct |
4 ms |
4696 KB |
Output is correct |
16 |
Correct |
3 ms |
4680 KB |
Output is correct |
17 |
Correct |
25 ms |
7044 KB |
Output is correct |
18 |
Correct |
32 ms |
7160 KB |
Output is correct |
19 |
Correct |
27 ms |
7452 KB |
Output is correct |
20 |
Correct |
28 ms |
7372 KB |
Output is correct |
21 |
Correct |
26 ms |
7436 KB |
Output is correct |
22 |
Correct |
25 ms |
7464 KB |
Output is correct |
23 |
Correct |
37 ms |
7132 KB |
Output is correct |
24 |
Correct |
28 ms |
7280 KB |
Output is correct |
25 |
Correct |
25 ms |
7308 KB |
Output is correct |
26 |
Correct |
26 ms |
7196 KB |
Output is correct |
27 |
Correct |
24 ms |
7236 KB |
Output is correct |
28 |
Correct |
24 ms |
7436 KB |
Output is correct |
29 |
Correct |
5 ms |
4188 KB |
Output is correct |
30 |
Correct |
5 ms |
4700 KB |
Output is correct |
31 |
Correct |
4 ms |
4444 KB |
Output is correct |
32 |
Correct |
4 ms |
4952 KB |
Output is correct |
33 |
Correct |
4 ms |
4696 KB |
Output is correct |
34 |
Correct |
3 ms |
4700 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
28 ms |
6688 KB |
Output is correct |
37 |
Correct |
31 ms |
7184 KB |
Output is correct |
38 |
Correct |
29 ms |
7308 KB |
Output is correct |
39 |
Correct |
27 ms |
7440 KB |
Output is correct |
40 |
Correct |
26 ms |
7560 KB |
Output is correct |
41 |
Correct |
3 ms |
4700 KB |
Output is correct |
42 |
Correct |
31 ms |
7256 KB |
Output is correct |
43 |
Correct |
28 ms |
7248 KB |
Output is correct |
44 |
Correct |
29 ms |
7296 KB |
Output is correct |
45 |
Correct |
25 ms |
7200 KB |
Output is correct |
46 |
Correct |
28 ms |
7496 KB |
Output is correct |
47 |
Correct |
24 ms |
7436 KB |
Output is correct |