# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
978235 |
2024-05-09T04:21:08 Z |
tamir1 |
Mutating DNA (IOI21_dna) |
C++17 |
|
41 ms |
8652 KB |
#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
string t="#",s="#";
int n,i,A1[100005],C1[100005],T1[100005],A2[100005],C2[100005],T2[100005],AC[100005],CA[100005],AT[100005],TA[100005],CT[100005],TC[100005];
void init(std::string a, std::string b) {
n=a.size();
s+=a;
t+=b;
for(i=1;i<=n;i++){
A1[i]=A1[i-1]+(s[i]=='A');
C1[i]=C1[i-1]+(s[i]=='C');
T1[i]=T1[i-1]+(s[i]=='T');
A2[i]=A2[i-1]+(t[i]=='A');
C2[i]=C2[i-1]+(t[i]=='C');
T2[i]=T2[i-1]+(t[i]=='T');
AC[i]=AC[i-1]+(s[i]=='A' && t[i]=='C');
CA[i]=CA[i-1]+(s[i]=='C' && t[i]=='A');
AT[i]=AT[i-1]+(s[i]=='A' && t[i]=='T');
TA[i]=TA[i-1]+(s[i]=='T' && t[i]=='A');
CT[i]=CT[i-1]+(s[i]=='C' && t[i]=='T');
TC[i]=TC[i-1]+(s[i]=='T' && t[i]=='C');
}
}
int a1,a2,c1,c2,t1,t2,ac,ca,at,ta,ct,tc,ans;
int get_distance(int x, int y) {
ans=0;
y++;
a1=A1[y]-A1[x];
a2=A2[y]-A2[x];
c1=C1[y]-C1[x];
c2=C2[y]-C2[x];
t1=T1[y]-T1[x];
t2=T2[y]-T2[x];
ac=AC[y]-AC[x];
at=AT[y]-AT[x];
ca=CA[y]-CA[x];
ct=CT[y]-CT[x];
ta=TA[y]-TA[x];
tc=TC[y]-TC[x];
if(a1!=a2 || c1!=c2 || t1!=t2) return -1;
if(ac > ca) {ans+=ca,ac-=ca,ca=0;}
else {ans+=ac,ca-=ac,ac=0;}
if(at > ta) {ans+=ta,at-=ta,ta=0;}
else {ans+=at,ta-=at,at=0;}
if(ct > tc) {ans+=tc,ct-=tc,tc=0;}
else {ans+=ct,tc-=ct,ct=0;}
//cout << ac << " " << ct << " " << ta << "\n";
//cout << ca << " " << at << " " << tc << "\n";
return ans+ac*2+ca*2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
7576 KB |
Output is correct |
2 |
Correct |
33 ms |
7984 KB |
Output is correct |
3 |
Correct |
33 ms |
7276 KB |
Output is correct |
4 |
Correct |
26 ms |
7768 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
608 KB |
Output is correct |
7 |
Correct |
0 ms |
352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
5784 KB |
Output is correct |
5 |
Correct |
5 ms |
5752 KB |
Output is correct |
6 |
Correct |
5 ms |
6236 KB |
Output is correct |
7 |
Correct |
5 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5980 KB |
Output is correct |
9 |
Correct |
4 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
5784 KB |
Output is correct |
5 |
Correct |
5 ms |
5752 KB |
Output is correct |
6 |
Correct |
5 ms |
6236 KB |
Output is correct |
7 |
Correct |
5 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5980 KB |
Output is correct |
9 |
Correct |
4 ms |
6016 KB |
Output is correct |
10 |
Correct |
36 ms |
7916 KB |
Output is correct |
11 |
Correct |
26 ms |
8024 KB |
Output is correct |
12 |
Correct |
36 ms |
8148 KB |
Output is correct |
13 |
Correct |
31 ms |
8168 KB |
Output is correct |
14 |
Correct |
41 ms |
8352 KB |
Output is correct |
15 |
Correct |
27 ms |
7544 KB |
Output is correct |
16 |
Correct |
27 ms |
8072 KB |
Output is correct |
17 |
Correct |
28 ms |
8088 KB |
Output is correct |
18 |
Correct |
33 ms |
8372 KB |
Output is correct |
19 |
Correct |
38 ms |
8636 KB |
Output is correct |
20 |
Correct |
37 ms |
8112 KB |
Output is correct |
21 |
Correct |
25 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
5784 KB |
Output is correct |
5 |
Correct |
5 ms |
5752 KB |
Output is correct |
6 |
Correct |
5 ms |
6236 KB |
Output is correct |
7 |
Correct |
5 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5980 KB |
Output is correct |
9 |
Correct |
4 ms |
6016 KB |
Output is correct |
10 |
Correct |
4 ms |
5496 KB |
Output is correct |
11 |
Correct |
5 ms |
5980 KB |
Output is correct |
12 |
Correct |
5 ms |
5684 KB |
Output is correct |
13 |
Correct |
5 ms |
5980 KB |
Output is correct |
14 |
Correct |
4 ms |
5976 KB |
Output is correct |
15 |
Correct |
5 ms |
6040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
7576 KB |
Output is correct |
2 |
Correct |
33 ms |
7984 KB |
Output is correct |
3 |
Correct |
33 ms |
7276 KB |
Output is correct |
4 |
Correct |
26 ms |
7768 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
608 KB |
Output is correct |
7 |
Correct |
0 ms |
352 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
5784 KB |
Output is correct |
12 |
Correct |
5 ms |
5752 KB |
Output is correct |
13 |
Correct |
5 ms |
6236 KB |
Output is correct |
14 |
Correct |
5 ms |
5468 KB |
Output is correct |
15 |
Correct |
4 ms |
5980 KB |
Output is correct |
16 |
Correct |
4 ms |
6016 KB |
Output is correct |
17 |
Correct |
36 ms |
7916 KB |
Output is correct |
18 |
Correct |
26 ms |
8024 KB |
Output is correct |
19 |
Correct |
36 ms |
8148 KB |
Output is correct |
20 |
Correct |
31 ms |
8168 KB |
Output is correct |
21 |
Correct |
41 ms |
8352 KB |
Output is correct |
22 |
Correct |
27 ms |
7544 KB |
Output is correct |
23 |
Correct |
27 ms |
8072 KB |
Output is correct |
24 |
Correct |
28 ms |
8088 KB |
Output is correct |
25 |
Correct |
33 ms |
8372 KB |
Output is correct |
26 |
Correct |
38 ms |
8636 KB |
Output is correct |
27 |
Correct |
37 ms |
8112 KB |
Output is correct |
28 |
Correct |
25 ms |
8540 KB |
Output is correct |
29 |
Correct |
4 ms |
5496 KB |
Output is correct |
30 |
Correct |
5 ms |
5980 KB |
Output is correct |
31 |
Correct |
5 ms |
5684 KB |
Output is correct |
32 |
Correct |
5 ms |
5980 KB |
Output is correct |
33 |
Correct |
4 ms |
5976 KB |
Output is correct |
34 |
Correct |
5 ms |
6040 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
27 ms |
7672 KB |
Output is correct |
37 |
Correct |
38 ms |
8284 KB |
Output is correct |
38 |
Correct |
32 ms |
7916 KB |
Output is correct |
39 |
Correct |
32 ms |
8140 KB |
Output is correct |
40 |
Correct |
30 ms |
8644 KB |
Output is correct |
41 |
Correct |
4 ms |
5988 KB |
Output is correct |
42 |
Correct |
34 ms |
8188 KB |
Output is correct |
43 |
Correct |
30 ms |
8500 KB |
Output is correct |
44 |
Correct |
30 ms |
8652 KB |
Output is correct |
45 |
Correct |
27 ms |
8292 KB |
Output is correct |
46 |
Correct |
26 ms |
8612 KB |
Output is correct |
47 |
Correct |
34 ms |
8548 KB |
Output is correct |