# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
437090 |
2021-06-25T18:55:39 Z |
T0p_ |
Mutating DNA (IOI21_dna) |
C++17 |
|
62 ms |
7492 KB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
int cnt_char[2][3][N], cnt_dif[6][N];
map<char, int> mp_char;
map<string, int> mp_str;
string a, b;
string get_string(int i)
{
string ret = "";
ret += a[i];
ret += b[i];
return ret;
}
void init(string _a, string _b)
{
a = _a, b = _b;
n = a.length();
mp_char['A'] = 0;
mp_char['T'] = 1;
mp_char['C'] = 2;
mp_str["AT"] = 0;
mp_str["AC"] = 1;
mp_str["TA"] = 2;
mp_str["TC"] = 3;
mp_str["CA"] = 4;
mp_str["CT"] = 5;
cnt_char[0][mp_char[a[0]]][1]++;
cnt_char[1][mp_char[b[0]]][1]++;
if(a[0] != b[0]) cnt_dif[mp_str[get_string(0)]][1]++;
for(int i=2 ; i<=n ; i++)
{
cnt_char[0][mp_char[a[i-1]]][i]++;
cnt_char[1][mp_char[b[i-1]]][i]++;
for(int j=0 ; j<3 ; j++)
{
cnt_char[0][j][i] += cnt_char[0][j][i-1];
cnt_char[1][j][i] += cnt_char[1][j][i-1];
}
if(a[i-1] != b[i-1]) cnt_dif[mp_str[get_string(i-1)]][i]++;
for(int j=0 ; j<6 ; j++) cnt_dif[j][i] += cnt_dif[j][i-1];
}
}
int get_distance(int x, int y)
{
x++, y++;
for(int j=0 ; j<3 ; j++) if(cnt_char[0][j][y]-cnt_char[0][j][x-1] != cnt_char[1][j][y]-cnt_char[1][j][x-1]) return -1;
int ret = 0, mn;
int at = cnt_dif[0][y] - cnt_dif[0][x-1];
int ac = cnt_dif[1][y] - cnt_dif[1][x-1];
int ta = cnt_dif[2][y] - cnt_dif[2][x-1];
int tc = cnt_dif[3][y] - cnt_dif[3][x-1];
int ca = cnt_dif[4][y] - cnt_dif[4][x-1];
int ct = cnt_dif[5][y] - cnt_dif[5][x-1];
mn = min(at, ta);
ret += mn;
at -= mn;
ta -= mn;
mn = min(ac, ca);
ret += mn;
ac -= mn;
ca -= mn;
mn = min(tc, ct);
ret += mn;
tc -= mn;
ct -= mn;
ret += at+at+ac+ac;
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
7088 KB |
Output is correct |
2 |
Correct |
52 ms |
7108 KB |
Output is correct |
3 |
Correct |
44 ms |
6584 KB |
Output is correct |
4 |
Correct |
47 ms |
7036 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
5708 KB |
Output is correct |
5 |
Correct |
9 ms |
5776 KB |
Output is correct |
6 |
Correct |
9 ms |
5728 KB |
Output is correct |
7 |
Correct |
9 ms |
5324 KB |
Output is correct |
8 |
Correct |
9 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
5708 KB |
Output is correct |
5 |
Correct |
9 ms |
5776 KB |
Output is correct |
6 |
Correct |
9 ms |
5728 KB |
Output is correct |
7 |
Correct |
9 ms |
5324 KB |
Output is correct |
8 |
Correct |
9 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
10 |
Correct |
45 ms |
7108 KB |
Output is correct |
11 |
Correct |
62 ms |
7108 KB |
Output is correct |
12 |
Correct |
46 ms |
7072 KB |
Output is correct |
13 |
Correct |
46 ms |
7220 KB |
Output is correct |
14 |
Correct |
48 ms |
7364 KB |
Output is correct |
15 |
Correct |
44 ms |
7364 KB |
Output is correct |
16 |
Correct |
43 ms |
7112 KB |
Output is correct |
17 |
Correct |
45 ms |
7384 KB |
Output is correct |
18 |
Correct |
44 ms |
7492 KB |
Output is correct |
19 |
Correct |
41 ms |
7108 KB |
Output is correct |
20 |
Correct |
53 ms |
7268 KB |
Output is correct |
21 |
Correct |
46 ms |
7488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
5708 KB |
Output is correct |
5 |
Correct |
9 ms |
5776 KB |
Output is correct |
6 |
Correct |
9 ms |
5728 KB |
Output is correct |
7 |
Correct |
9 ms |
5324 KB |
Output is correct |
8 |
Correct |
9 ms |
5708 KB |
Output is correct |
9 |
Correct |
7 ms |
5708 KB |
Output is correct |
10 |
Correct |
9 ms |
5324 KB |
Output is correct |
11 |
Correct |
10 ms |
5696 KB |
Output is correct |
12 |
Correct |
10 ms |
5452 KB |
Output is correct |
13 |
Correct |
10 ms |
5708 KB |
Output is correct |
14 |
Correct |
11 ms |
5720 KB |
Output is correct |
15 |
Correct |
8 ms |
5708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
7088 KB |
Output is correct |
2 |
Correct |
52 ms |
7108 KB |
Output is correct |
3 |
Correct |
44 ms |
6584 KB |
Output is correct |
4 |
Correct |
47 ms |
7036 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
9 ms |
5708 KB |
Output is correct |
12 |
Correct |
9 ms |
5776 KB |
Output is correct |
13 |
Correct |
9 ms |
5728 KB |
Output is correct |
14 |
Correct |
9 ms |
5324 KB |
Output is correct |
15 |
Correct |
9 ms |
5708 KB |
Output is correct |
16 |
Correct |
7 ms |
5708 KB |
Output is correct |
17 |
Correct |
45 ms |
7108 KB |
Output is correct |
18 |
Correct |
62 ms |
7108 KB |
Output is correct |
19 |
Correct |
46 ms |
7072 KB |
Output is correct |
20 |
Correct |
46 ms |
7220 KB |
Output is correct |
21 |
Correct |
48 ms |
7364 KB |
Output is correct |
22 |
Correct |
44 ms |
7364 KB |
Output is correct |
23 |
Correct |
43 ms |
7112 KB |
Output is correct |
24 |
Correct |
45 ms |
7384 KB |
Output is correct |
25 |
Correct |
44 ms |
7492 KB |
Output is correct |
26 |
Correct |
41 ms |
7108 KB |
Output is correct |
27 |
Correct |
53 ms |
7268 KB |
Output is correct |
28 |
Correct |
46 ms |
7488 KB |
Output is correct |
29 |
Correct |
9 ms |
5324 KB |
Output is correct |
30 |
Correct |
10 ms |
5696 KB |
Output is correct |
31 |
Correct |
10 ms |
5452 KB |
Output is correct |
32 |
Correct |
10 ms |
5708 KB |
Output is correct |
33 |
Correct |
11 ms |
5720 KB |
Output is correct |
34 |
Correct |
8 ms |
5708 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
48 ms |
6680 KB |
Output is correct |
37 |
Correct |
45 ms |
7088 KB |
Output is correct |
38 |
Correct |
48 ms |
7236 KB |
Output is correct |
39 |
Correct |
52 ms |
7408 KB |
Output is correct |
40 |
Correct |
50 ms |
7416 KB |
Output is correct |
41 |
Correct |
7 ms |
5708 KB |
Output is correct |
42 |
Correct |
44 ms |
7128 KB |
Output is correct |
43 |
Correct |
47 ms |
7468 KB |
Output is correct |
44 |
Correct |
45 ms |
7464 KB |
Output is correct |
45 |
Correct |
54 ms |
7212 KB |
Output is correct |
46 |
Correct |
43 ms |
7432 KB |
Output is correct |
47 |
Correct |
45 ms |
7472 KB |
Output is correct |