# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
530882 | 2022-02-27T04:22:42 Z | knon0501 | Mutating DNA (IOI21_dna) | C++17 | 61 ms | 9940 KB |
#include<bits/stdc++.h> using namespace std; int sa[100005][3]; int sb[100005][3]; int e[100005][3][3]; int c[200]; int n; string a,b; void init(std::string aa, std::string bb) { a=aa; b=bb; n=a.length(); c['A']=0; c['T']=1; c['C']=2; for(int i=1 ; i<=n ; i++){ sa[i][0]=sa[i-1][0]; sb[i][0]=sb[i-1][0]; sa[i][1]=sa[i-1][1]; sb[i][1]=sb[i-1][1]; sa[i][2]=sa[i-1][2]; sb[i][2]=sb[i-1][2]; sa[i][c[a[i-1]]]++; sb[i][c[b[i-1]]]++; for(int j=0 ; j<3 ; j++) for(int k=0 ; k<3 ; k++) e[i][j][k]=e[i-1][j][k]; e[i][c[a[i-1]]][c[b[i-1]]]++; } } int get_distance(int x, int y) { x++; y++; for(int i=0 ; i<3 ; i++) if(sa[y][i]-sa[x-1][i]!=sb[y][i]-sb[x-1][i])return -1; int d[3][3]={0,}; for(int i=0 ; i<3 ; i++) for(int j=0 ; j<3 ; j++) d[i][j]=e[y][i][j]-e[x-1][i][j]; int ans=0; int cnt=0; for(int i=0 ; i<3 ; i++){ for(int j=0 ; j<3 ; j++){ int k=min(d[i][j],d[j][i]); d[i][j]-=k; if(i!=j) d[j][i]-=k; if(i!=j) ans+=k; cnt+=d[i][j]; } } return ans+cnt*2/3; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 8312 KB | Output is correct |
2 | Correct | 49 ms | 9584 KB | Output is correct |
3 | Correct | 42 ms | 9028 KB | Output is correct |
4 | Correct | 42 ms | 9648 KB | Output is correct |
5 | Correct | 0 ms | 300 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 6 ms | 6860 KB | Output is correct |
5 | Correct | 6 ms | 7116 KB | Output is correct |
6 | Correct | 7 ms | 7084 KB | Output is correct |
7 | Correct | 7 ms | 6604 KB | Output is correct |
8 | Correct | 7 ms | 7092 KB | Output is correct |
9 | Correct | 6 ms | 7116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 6 ms | 6860 KB | Output is correct |
5 | Correct | 6 ms | 7116 KB | Output is correct |
6 | Correct | 7 ms | 7084 KB | Output is correct |
7 | Correct | 7 ms | 6604 KB | Output is correct |
8 | Correct | 7 ms | 7092 KB | Output is correct |
9 | Correct | 6 ms | 7116 KB | Output is correct |
10 | Correct | 36 ms | 9576 KB | Output is correct |
11 | Correct | 37 ms | 9652 KB | Output is correct |
12 | Correct | 38 ms | 9404 KB | Output is correct |
13 | Correct | 48 ms | 9708 KB | Output is correct |
14 | Correct | 42 ms | 9924 KB | Output is correct |
15 | Correct | 37 ms | 9916 KB | Output is correct |
16 | Correct | 34 ms | 9360 KB | Output is correct |
17 | Correct | 34 ms | 9628 KB | Output is correct |
18 | Correct | 36 ms | 9912 KB | Output is correct |
19 | Correct | 46 ms | 9356 KB | Output is correct |
20 | Correct | 32 ms | 9600 KB | Output is correct |
21 | Correct | 32 ms | 9924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 6 ms | 6860 KB | Output is correct |
5 | Correct | 6 ms | 7116 KB | Output is correct |
6 | Correct | 7 ms | 7084 KB | Output is correct |
7 | Correct | 7 ms | 6604 KB | Output is correct |
8 | Correct | 7 ms | 7092 KB | Output is correct |
9 | Correct | 6 ms | 7116 KB | Output is correct |
10 | Correct | 6 ms | 6476 KB | Output is correct |
11 | Correct | 6 ms | 7128 KB | Output is correct |
12 | Correct | 6 ms | 6596 KB | Output is correct |
13 | Correct | 6 ms | 7080 KB | Output is correct |
14 | Correct | 6 ms | 7092 KB | Output is correct |
15 | Correct | 6 ms | 7040 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 8312 KB | Output is correct |
2 | Correct | 49 ms | 9584 KB | Output is correct |
3 | Correct | 42 ms | 9028 KB | Output is correct |
4 | Correct | 42 ms | 9648 KB | Output is correct |
5 | Correct | 0 ms | 300 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 6 ms | 6860 KB | Output is correct |
12 | Correct | 6 ms | 7116 KB | Output is correct |
13 | Correct | 7 ms | 7084 KB | Output is correct |
14 | Correct | 7 ms | 6604 KB | Output is correct |
15 | Correct | 7 ms | 7092 KB | Output is correct |
16 | Correct | 6 ms | 7116 KB | Output is correct |
17 | Correct | 36 ms | 9576 KB | Output is correct |
18 | Correct | 37 ms | 9652 KB | Output is correct |
19 | Correct | 38 ms | 9404 KB | Output is correct |
20 | Correct | 48 ms | 9708 KB | Output is correct |
21 | Correct | 42 ms | 9924 KB | Output is correct |
22 | Correct | 37 ms | 9916 KB | Output is correct |
23 | Correct | 34 ms | 9360 KB | Output is correct |
24 | Correct | 34 ms | 9628 KB | Output is correct |
25 | Correct | 36 ms | 9912 KB | Output is correct |
26 | Correct | 46 ms | 9356 KB | Output is correct |
27 | Correct | 32 ms | 9600 KB | Output is correct |
28 | Correct | 32 ms | 9924 KB | Output is correct |
29 | Correct | 6 ms | 6476 KB | Output is correct |
30 | Correct | 6 ms | 7128 KB | Output is correct |
31 | Correct | 6 ms | 6596 KB | Output is correct |
32 | Correct | 6 ms | 7080 KB | Output is correct |
33 | Correct | 6 ms | 7092 KB | Output is correct |
34 | Correct | 6 ms | 7040 KB | Output is correct |
35 | Correct | 1 ms | 204 KB | Output is correct |
36 | Correct | 46 ms | 9008 KB | Output is correct |
37 | Correct | 37 ms | 9648 KB | Output is correct |
38 | Correct | 39 ms | 9616 KB | Output is correct |
39 | Correct | 61 ms | 9916 KB | Output is correct |
40 | Correct | 40 ms | 9940 KB | Output is correct |
41 | Correct | 6 ms | 7092 KB | Output is correct |
42 | Correct | 36 ms | 9480 KB | Output is correct |
43 | Correct | 36 ms | 9904 KB | Output is correct |
44 | Correct | 44 ms | 9892 KB | Output is correct |
45 | Correct | 33 ms | 9496 KB | Output is correct |
46 | Correct | 32 ms | 9936 KB | Output is correct |
47 | Correct | 40 ms | 9912 KB | Output is correct |