# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
585325 | 2022-06-28T16:05:28 Z | cfalas | Mutating DNA (IOI21_dna) | C++17 | 46 ms | 10220 KB |
#include "dna.h" #include<bits/stdc++.h> using namespace std; int m[3][3][200000]; int x[256]; int cc[200000]; int Aa[200000]; int Ta[200000]; int Ca[200000]; int Ab[200000]; int Tb[200000]; int Cb[200000]; void init(std::string a, std::string b) { x['A'] = 0; x['T'] = 1; x['C'] = 2; int n = a.size(); for(int i=0;i<n;i++){ Aa[i+1] = Aa[i] + (a[i]=='A'); Ta[i+1] = Ta[i] + (a[i]=='T'); Ca[i+1] = Ca[i] + (a[i]=='C'); Ab[i+1] = Ab[i] + (b[i]=='A'); Tb[i+1] = Tb[i] + (b[i]=='T'); Cb[i+1] = Cb[i] + (b[i]=='C'); for(int j=0;j<3;j++){ for(int k=0;k<3;k++) m[j][k][i+1] = m[j][k][i]; } m[x[a[i]]][x[b[i]]][i+1] = m[x[a[i]]][x[b[i]]][i] + 1; cc[i+1] = cc[i] + (a[i]==b[i]); //cout<<Aa[i+1]<<" "<<Ta[i+1]<<" "<<Ca[i+1]<<" "<<cc[i+1]<<endl; } } int get_distance(int x, int y) { x++, y++; if(Aa[y]-Aa[x-1] != Ab[y]-Ab[x-1]) return -1; if(Ta[y]-Ta[x-1] != Tb[y]-Tb[x-1]) return -1; if(Ca[y]-Ca[x-1] != Cb[y]-Cb[x-1]) return -1; int tot=0; int tot2=0; for(int i=0;i<3;i++){ for(int j=i+1;j<3;j++){ tot += abs((m[i][j][y]-m[i][j][x-1]) - (m[j][i][y]-m[j][i][x-1])); tot2 += min((m[i][j][y]-m[i][j][x-1]), (m[j][i][y]-m[j][i][x-1])); } } //cout<<tot2<<" "<<tot<<endl; return tot/3 * 2 + tot2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 8400 KB | Output is correct |
2 | Correct | 34 ms | 8456 KB | Output is correct |
3 | Correct | 33 ms | 7928 KB | Output is correct |
4 | Correct | 36 ms | 8456 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 6 ms | 7036 KB | Output is correct |
5 | Correct | 7 ms | 7152 KB | Output is correct |
6 | Correct | 5 ms | 7124 KB | Output is correct |
7 | Correct | 6 ms | 6812 KB | Output is correct |
8 | Correct | 5 ms | 7124 KB | Output is correct |
9 | Correct | 5 ms | 7124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 6 ms | 7036 KB | Output is correct |
5 | Correct | 7 ms | 7152 KB | Output is correct |
6 | Correct | 5 ms | 7124 KB | Output is correct |
7 | Correct | 6 ms | 6812 KB | Output is correct |
8 | Correct | 5 ms | 7124 KB | Output is correct |
9 | Correct | 5 ms | 7124 KB | Output is correct |
10 | Correct | 40 ms | 8468 KB | Output is correct |
11 | Correct | 36 ms | 8492 KB | Output is correct |
12 | Correct | 35 ms | 8316 KB | Output is correct |
13 | Correct | 36 ms | 8468 KB | Output is correct |
14 | Correct | 35 ms | 8856 KB | Output is correct |
15 | Correct | 46 ms | 8720 KB | Output is correct |
16 | Correct | 32 ms | 8420 KB | Output is correct |
17 | Correct | 33 ms | 8588 KB | Output is correct |
18 | Correct | 32 ms | 8800 KB | Output is correct |
19 | Correct | 30 ms | 8428 KB | Output is correct |
20 | Correct | 30 ms | 8588 KB | Output is correct |
21 | Correct | 31 ms | 8840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 6 ms | 7036 KB | Output is correct |
5 | Correct | 7 ms | 7152 KB | Output is correct |
6 | Correct | 5 ms | 7124 KB | Output is correct |
7 | Correct | 6 ms | 6812 KB | Output is correct |
8 | Correct | 5 ms | 7124 KB | Output is correct |
9 | Correct | 5 ms | 7124 KB | Output is correct |
10 | Correct | 5 ms | 6612 KB | Output is correct |
11 | Correct | 6 ms | 7124 KB | Output is correct |
12 | Correct | 5 ms | 6756 KB | Output is correct |
13 | Correct | 8 ms | 7380 KB | Output is correct |
14 | Correct | 5 ms | 7356 KB | Output is correct |
15 | Correct | 6 ms | 7380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 8400 KB | Output is correct |
2 | Correct | 34 ms | 8456 KB | Output is correct |
3 | Correct | 33 ms | 7928 KB | Output is correct |
4 | Correct | 36 ms | 8456 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 6 ms | 7036 KB | Output is correct |
12 | Correct | 7 ms | 7152 KB | Output is correct |
13 | Correct | 5 ms | 7124 KB | Output is correct |
14 | Correct | 6 ms | 6812 KB | Output is correct |
15 | Correct | 5 ms | 7124 KB | Output is correct |
16 | Correct | 5 ms | 7124 KB | Output is correct |
17 | Correct | 40 ms | 8468 KB | Output is correct |
18 | Correct | 36 ms | 8492 KB | Output is correct |
19 | Correct | 35 ms | 8316 KB | Output is correct |
20 | Correct | 36 ms | 8468 KB | Output is correct |
21 | Correct | 35 ms | 8856 KB | Output is correct |
22 | Correct | 46 ms | 8720 KB | Output is correct |
23 | Correct | 32 ms | 8420 KB | Output is correct |
24 | Correct | 33 ms | 8588 KB | Output is correct |
25 | Correct | 32 ms | 8800 KB | Output is correct |
26 | Correct | 30 ms | 8428 KB | Output is correct |
27 | Correct | 30 ms | 8588 KB | Output is correct |
28 | Correct | 31 ms | 8840 KB | Output is correct |
29 | Correct | 5 ms | 6612 KB | Output is correct |
30 | Correct | 6 ms | 7124 KB | Output is correct |
31 | Correct | 5 ms | 6756 KB | Output is correct |
32 | Correct | 8 ms | 7380 KB | Output is correct |
33 | Correct | 5 ms | 7356 KB | Output is correct |
34 | Correct | 6 ms | 7380 KB | Output is correct |
35 | Correct | 0 ms | 340 KB | Output is correct |
36 | Correct | 34 ms | 9244 KB | Output is correct |
37 | Correct | 35 ms | 9792 KB | Output is correct |
38 | Correct | 37 ms | 9796 KB | Output is correct |
39 | Correct | 37 ms | 10136 KB | Output is correct |
40 | Correct | 35 ms | 10220 KB | Output is correct |
41 | Correct | 6 ms | 7380 KB | Output is correct |
42 | Correct | 38 ms | 9620 KB | Output is correct |
43 | Correct | 39 ms | 10104 KB | Output is correct |
44 | Correct | 35 ms | 10120 KB | Output is correct |
45 | Correct | 31 ms | 9748 KB | Output is correct |
46 | Correct | 32 ms | 10100 KB | Output is correct |
47 | Correct | 36 ms | 10124 KB | Output is correct |