# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
607319 | 2022-07-26T15:17:10 Z | wiktorlew | Mutating DNA (IOI21_dna) | C++17 | 43 ms | 8600 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int ile[N][3][2], line[N][3][2]; int tsf(char c){ if(c=='A') return 0; if(c=='C') return 1; if(c=='T') return 2; } void init(string a, string b){ for(int i=0;i<a.length();i++){ ile[i+1][tsf(a[i])][0]++; ile[i+1][tsf(b[i])][1]++; if(a[i]=='A'&&b[i]=='C') line[i+1][0][0]++; if(a[i]=='A'&&b[i]=='T')line[i+1][1][0]++; if(a[i]=='C'&&b[i]=='T')line[i+1][2][0]++; if(a[i]=='C'&&b[i]=='A') line[i+1][0][1]++; if(a[i]=='T'&&b[i]=='A')line[i+1][1][1]++; if(a[i]=='T'&&b[i]=='C')line[i+1][2][1]++; for(int j=0;j<=2;j++){ ile[i+1][j][0]+=ile[i][j][0]; ile[i+1][j][1]+=ile[i][j][1]; line[i+1][j][0]+=line[i][j][0]; line[i+1][j][1]+=line[i][j][1]; } } } int get_distance(int x, int y){ x++; y++; if(ile[y][0][0]-ile[x-1][0][0]!=ile[y][0][1]-ile[x-1][0][1]){ return -1; } if(ile[y][1][0]-ile[x-1][1][0]!=ile[y][1][1]-ile[x-1][1][1]){ return -1; } if(ile[y][2][0]-ile[x-1][2][0]!=ile[y][2][1]-ile[x-1][2][1]){ return -1; } int wynik=0, err=0; for(int i=0;i<=2;i++){ int pom1 = line[y][i][0]-line[x-1][i][0]; int pom2 = line[y][i][1]-line[x-1][i][1]; wynik+=(min(pom1, pom2)); err+=abs(pom1-pom2); } wynik+=(err/3)*2; return wynik; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 6804 KB | Output is correct |
2 | Correct | 33 ms | 6832 KB | Output is correct |
3 | Correct | 34 ms | 6396 KB | Output is correct |
4 | Correct | 33 ms | 6792 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 5 ms | 5460 KB | Output is correct |
5 | Correct | 6 ms | 5520 KB | Output is correct |
6 | Correct | 5 ms | 5460 KB | Output is correct |
7 | Correct | 5 ms | 5204 KB | Output is correct |
8 | Correct | 5 ms | 5588 KB | Output is correct |
9 | Correct | 4 ms | 5588 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 5 ms | 5460 KB | Output is correct |
5 | Correct | 6 ms | 5520 KB | Output is correct |
6 | Correct | 5 ms | 5460 KB | Output is correct |
7 | Correct | 5 ms | 5204 KB | Output is correct |
8 | Correct | 5 ms | 5588 KB | Output is correct |
9 | Correct | 4 ms | 5588 KB | Output is correct |
10 | Correct | 32 ms | 6796 KB | Output is correct |
11 | Correct | 32 ms | 6776 KB | Output is correct |
12 | Correct | 31 ms | 6888 KB | Output is correct |
13 | Correct | 43 ms | 6980 KB | Output is correct |
14 | Correct | 43 ms | 7288 KB | Output is correct |
15 | Correct | 33 ms | 7180 KB | Output is correct |
16 | Correct | 31 ms | 6808 KB | Output is correct |
17 | Correct | 31 ms | 6940 KB | Output is correct |
18 | Correct | 31 ms | 7176 KB | Output is correct |
19 | Correct | 34 ms | 7028 KB | Output is correct |
20 | Correct | 39 ms | 7100 KB | Output is correct |
21 | Correct | 28 ms | 7176 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 5 ms | 5460 KB | Output is correct |
5 | Correct | 6 ms | 5520 KB | Output is correct |
6 | Correct | 5 ms | 5460 KB | Output is correct |
7 | Correct | 5 ms | 5204 KB | Output is correct |
8 | Correct | 5 ms | 5588 KB | Output is correct |
9 | Correct | 4 ms | 5588 KB | Output is correct |
10 | Correct | 5 ms | 5076 KB | Output is correct |
11 | Correct | 5 ms | 5460 KB | Output is correct |
12 | Correct | 5 ms | 5204 KB | Output is correct |
13 | Correct | 6 ms | 5660 KB | Output is correct |
14 | Correct | 6 ms | 5700 KB | Output is correct |
15 | Correct | 6 ms | 5716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 6804 KB | Output is correct |
2 | Correct | 33 ms | 6832 KB | Output is correct |
3 | Correct | 34 ms | 6396 KB | Output is correct |
4 | Correct | 33 ms | 6792 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 5 ms | 5460 KB | Output is correct |
12 | Correct | 6 ms | 5520 KB | Output is correct |
13 | Correct | 5 ms | 5460 KB | Output is correct |
14 | Correct | 5 ms | 5204 KB | Output is correct |
15 | Correct | 5 ms | 5588 KB | Output is correct |
16 | Correct | 4 ms | 5588 KB | Output is correct |
17 | Correct | 32 ms | 6796 KB | Output is correct |
18 | Correct | 32 ms | 6776 KB | Output is correct |
19 | Correct | 31 ms | 6888 KB | Output is correct |
20 | Correct | 43 ms | 6980 KB | Output is correct |
21 | Correct | 43 ms | 7288 KB | Output is correct |
22 | Correct | 33 ms | 7180 KB | Output is correct |
23 | Correct | 31 ms | 6808 KB | Output is correct |
24 | Correct | 31 ms | 6940 KB | Output is correct |
25 | Correct | 31 ms | 7176 KB | Output is correct |
26 | Correct | 34 ms | 7028 KB | Output is correct |
27 | Correct | 39 ms | 7100 KB | Output is correct |
28 | Correct | 28 ms | 7176 KB | Output is correct |
29 | Correct | 5 ms | 5076 KB | Output is correct |
30 | Correct | 5 ms | 5460 KB | Output is correct |
31 | Correct | 5 ms | 5204 KB | Output is correct |
32 | Correct | 6 ms | 5660 KB | Output is correct |
33 | Correct | 6 ms | 5700 KB | Output is correct |
34 | Correct | 6 ms | 5716 KB | Output is correct |
35 | Correct | 1 ms | 212 KB | Output is correct |
36 | Correct | 40 ms | 7740 KB | Output is correct |
37 | Correct | 35 ms | 8116 KB | Output is correct |
38 | Correct | 35 ms | 8156 KB | Output is correct |
39 | Correct | 39 ms | 8600 KB | Output is correct |
40 | Correct | 33 ms | 8568 KB | Output is correct |
41 | Correct | 4 ms | 5716 KB | Output is correct |
42 | Correct | 32 ms | 8084 KB | Output is correct |
43 | Correct | 31 ms | 8456 KB | Output is correct |
44 | Correct | 31 ms | 8436 KB | Output is correct |
45 | Correct | 30 ms | 8160 KB | Output is correct |
46 | Correct | 29 ms | 8456 KB | Output is correct |
47 | Correct | 30 ms | 8440 KB | Output is correct |