# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
979968 | 2024-05-11T17:50:52 Z | batsukh2006 | Mutating DNA (IOI21_dna) | C++17 | 45 ms | 9836 KB |
#include "dna.h" #include<bits/stdc++.h> using namespace std; const int mxN=1e5+1; int mp[mxN][3][3]; int f[mxN][3],s[mxN][3]; void init(string a, string b){ map<char,int> m; m['A']=0; m['T']=1; m['C']=2; for(int i=1; i<=a.size(); i++){ for(int j=0; j<3; j++){ f[i][j]=f[i-1][j]; s[i][j]=s[i-1][j]; for(int k=0; k<3; k++){ mp[i][j][k]=mp[i-1][j][k]; } } f[i][m[a[i-1]]]++; s[i][m[b[i-1]]]++; mp[i][m[a[i-1]]][m[b[i-1]]]++; } } int get_distance(int x, int y){ for(int i=0; i<3; i++){ if(f[y+1][i]-f[x][i]!=s[y+1][i]-s[x][i]){ return -1; } } int ans=0; int lft=y-x+1; for(int i=0; i<3; i++){ for(int j=i; j<3; j++){ if(i==j) lft-=min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]); else lft-=2*min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]); if(i!=j) ans+=min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]); } } return ans+lft/3*2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 8172 KB | Output is correct |
2 | Correct | 29 ms | 8792 KB | Output is correct |
3 | Correct | 28 ms | 8224 KB | Output is correct |
4 | Correct | 29 ms | 8764 KB | Output is correct |
5 | Correct | 1 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 | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 6 ms | 6876 KB | Output is correct |
5 | Correct | 6 ms | 6748 KB | Output is correct |
6 | Correct | 6 ms | 6748 KB | Output is correct |
7 | Correct | 5 ms | 6492 KB | Output is correct |
8 | Correct | 6 ms | 6964 KB | Output is correct |
9 | Correct | 5 ms | 6796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 6 ms | 6876 KB | Output is correct |
5 | Correct | 6 ms | 6748 KB | Output is correct |
6 | Correct | 6 ms | 6748 KB | Output is correct |
7 | Correct | 5 ms | 6492 KB | Output is correct |
8 | Correct | 6 ms | 6964 KB | Output is correct |
9 | Correct | 5 ms | 6796 KB | Output is correct |
10 | Correct | 29 ms | 8724 KB | Output is correct |
11 | Correct | 29 ms | 8888 KB | Output is correct |
12 | Correct | 30 ms | 8988 KB | Output is correct |
13 | Correct | 30 ms | 9016 KB | Output is correct |
14 | Correct | 38 ms | 9228 KB | Output is correct |
15 | Correct | 43 ms | 8464 KB | Output is correct |
16 | Correct | 32 ms | 8992 KB | Output is correct |
17 | Correct | 45 ms | 8548 KB | Output is correct |
18 | Correct | 34 ms | 9340 KB | Output is correct |
19 | Correct | 30 ms | 9244 KB | Output is correct |
20 | Correct | 34 ms | 8764 KB | Output is correct |
21 | Correct | 27 ms | 9200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 6 ms | 6876 KB | Output is correct |
5 | Correct | 6 ms | 6748 KB | Output is correct |
6 | Correct | 6 ms | 6748 KB | Output is correct |
7 | Correct | 5 ms | 6492 KB | Output is correct |
8 | Correct | 6 ms | 6964 KB | Output is correct |
9 | Correct | 5 ms | 6796 KB | Output is correct |
10 | Correct | 6 ms | 6236 KB | Output is correct |
11 | Correct | 6 ms | 7004 KB | Output is correct |
12 | Correct | 6 ms | 6352 KB | Output is correct |
13 | Correct | 6 ms | 6940 KB | Output is correct |
14 | Correct | 7 ms | 6860 KB | Output is correct |
15 | Correct | 5 ms | 7288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 8172 KB | Output is correct |
2 | Correct | 29 ms | 8792 KB | Output is correct |
3 | Correct | 28 ms | 8224 KB | Output is correct |
4 | Correct | 29 ms | 8764 KB | Output is correct |
5 | Correct | 1 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 | 1 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 6 ms | 6876 KB | Output is correct |
12 | Correct | 6 ms | 6748 KB | Output is correct |
13 | Correct | 6 ms | 6748 KB | Output is correct |
14 | Correct | 5 ms | 6492 KB | Output is correct |
15 | Correct | 6 ms | 6964 KB | Output is correct |
16 | Correct | 5 ms | 6796 KB | Output is correct |
17 | Correct | 29 ms | 8724 KB | Output is correct |
18 | Correct | 29 ms | 8888 KB | Output is correct |
19 | Correct | 30 ms | 8988 KB | Output is correct |
20 | Correct | 30 ms | 9016 KB | Output is correct |
21 | Correct | 38 ms | 9228 KB | Output is correct |
22 | Correct | 43 ms | 8464 KB | Output is correct |
23 | Correct | 32 ms | 8992 KB | Output is correct |
24 | Correct | 45 ms | 8548 KB | Output is correct |
25 | Correct | 34 ms | 9340 KB | Output is correct |
26 | Correct | 30 ms | 9244 KB | Output is correct |
27 | Correct | 34 ms | 8764 KB | Output is correct |
28 | Correct | 27 ms | 9200 KB | Output is correct |
29 | Correct | 6 ms | 6236 KB | Output is correct |
30 | Correct | 6 ms | 7004 KB | Output is correct |
31 | Correct | 6 ms | 6352 KB | Output is correct |
32 | Correct | 6 ms | 6940 KB | Output is correct |
33 | Correct | 7 ms | 6860 KB | Output is correct |
34 | Correct | 5 ms | 7288 KB | Output is correct |
35 | Correct | 1 ms | 348 KB | Output is correct |
36 | Correct | 32 ms | 8444 KB | Output is correct |
37 | Correct | 32 ms | 9460 KB | Output is correct |
38 | Correct | 38 ms | 8904 KB | Output is correct |
39 | Correct | 34 ms | 9012 KB | Output is correct |
40 | Correct | 33 ms | 9368 KB | Output is correct |
41 | Correct | 5 ms | 6852 KB | Output is correct |
42 | Correct | 31 ms | 9004 KB | Output is correct |
43 | Correct | 34 ms | 9180 KB | Output is correct |
44 | Correct | 32 ms | 9560 KB | Output is correct |
45 | Correct | 31 ms | 8904 KB | Output is correct |
46 | Correct | 31 ms | 9836 KB | Output is correct |
47 | Correct | 33 ms | 9232 KB | Output is correct |