# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
793775 |
2023-07-26T06:37:49 Z |
Johann |
Mutating DNA (IOI21_dna) |
C++17 |
|
105 ms |
13888 KB |
#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
#define sz(x) (int)(x).size()
vector<int> str[2];
int N;
struct node
{
int data[3][3];
node()
{
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
data[i][j] = 0;
}
};
node operator+(const node &a, const node &b)
{
node ret;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
ret.data[i][j] = a.data[i][j] + b.data[i][j];
return ret;
}
const node EMPTY;
struct segtree
{
int size;
vector<node> arr;
void init()
{
size = 1;
while (size < N)
size *= 2;
arr.resize(2 * size);
for (int i = 0; i < N; ++i)
++arr[size + i].data[str[0][i]][str[1][i]];
for (int i = size - 1; i > 0; --i)
arr[i] = arr[2 * i] + arr[2 * i + 1];
}
node query(int l, int r)
{
return query(l, r, 1, 0, size);
}
node query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return EMPTY;
int m = (lx + rx) / 2;
return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx);
}
};
segtree seg;
void init(std::string a, std::string b)
{
N = sz(a);
str[0].resize(N), str[1].resize(N);
vi trans(128, -1);
trans['A'] = 0;
trans['C'] = 1;
trans['T'] = 2;
for (int i = 0; i < N; ++i)
str[0][i] = trans[a[i]], str[1][i] = trans[b[i]];
seg.init();
}
int get_distance(int x, int y)
{
node tmp = seg.query(x, y + 1);
int moves = 0;
for (int i = 0; i < 3; ++i)
tmp.data[i][i] = 0;
int cnt[3] = {0, 0, 0};
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
cnt[i] += tmp.data[i][j], cnt[j] -= tmp.data[i][j];
for (int i = 0; i < 3; ++i)
if (cnt[i] != 0)
return -1;
int v = 0;
for (int i = 0; i < 3; ++i)
for (int j = i + 1; j < 3; ++j)
{
int mini = min(tmp.data[i][j], tmp.data[j][i]);
moves += mini;
tmp.data[i][j] -= mini;
tmp.data[j][i] -= mini;
v = max(v, max(tmp.data[i][j], tmp.data[j][i]));
}
moves += 2 * v;
return moves;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
13480 KB |
Output is correct |
2 |
Correct |
57 ms |
13488 KB |
Output is correct |
3 |
Correct |
55 ms |
13324 KB |
Output is correct |
4 |
Correct |
56 ms |
13484 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
11092 KB |
Output is correct |
5 |
Correct |
7 ms |
11060 KB |
Output is correct |
6 |
Correct |
7 ms |
11092 KB |
Output is correct |
7 |
Correct |
7 ms |
10964 KB |
Output is correct |
8 |
Correct |
7 ms |
11092 KB |
Output is correct |
9 |
Correct |
7 ms |
11092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
11092 KB |
Output is correct |
5 |
Correct |
7 ms |
11060 KB |
Output is correct |
6 |
Correct |
7 ms |
11092 KB |
Output is correct |
7 |
Correct |
7 ms |
10964 KB |
Output is correct |
8 |
Correct |
7 ms |
11092 KB |
Output is correct |
9 |
Correct |
7 ms |
11092 KB |
Output is correct |
10 |
Correct |
56 ms |
13496 KB |
Output is correct |
11 |
Correct |
55 ms |
13448 KB |
Output is correct |
12 |
Correct |
79 ms |
13712 KB |
Output is correct |
13 |
Correct |
91 ms |
13812 KB |
Output is correct |
14 |
Correct |
83 ms |
13888 KB |
Output is correct |
15 |
Correct |
77 ms |
13804 KB |
Output is correct |
16 |
Correct |
82 ms |
13668 KB |
Output is correct |
17 |
Correct |
77 ms |
13720 KB |
Output is correct |
18 |
Correct |
79 ms |
13784 KB |
Output is correct |
19 |
Correct |
70 ms |
13648 KB |
Output is correct |
20 |
Correct |
73 ms |
13676 KB |
Output is correct |
21 |
Correct |
71 ms |
13832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
11092 KB |
Output is correct |
5 |
Correct |
7 ms |
11060 KB |
Output is correct |
6 |
Correct |
7 ms |
11092 KB |
Output is correct |
7 |
Correct |
7 ms |
10964 KB |
Output is correct |
8 |
Correct |
7 ms |
11092 KB |
Output is correct |
9 |
Correct |
7 ms |
11092 KB |
Output is correct |
10 |
Correct |
7 ms |
10892 KB |
Output is correct |
11 |
Correct |
7 ms |
11028 KB |
Output is correct |
12 |
Correct |
9 ms |
11012 KB |
Output is correct |
13 |
Correct |
7 ms |
11060 KB |
Output is correct |
14 |
Correct |
7 ms |
11064 KB |
Output is correct |
15 |
Correct |
7 ms |
11092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
13480 KB |
Output is correct |
2 |
Correct |
57 ms |
13488 KB |
Output is correct |
3 |
Correct |
55 ms |
13324 KB |
Output is correct |
4 |
Correct |
56 ms |
13484 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
11092 KB |
Output is correct |
12 |
Correct |
7 ms |
11060 KB |
Output is correct |
13 |
Correct |
7 ms |
11092 KB |
Output is correct |
14 |
Correct |
7 ms |
10964 KB |
Output is correct |
15 |
Correct |
7 ms |
11092 KB |
Output is correct |
16 |
Correct |
7 ms |
11092 KB |
Output is correct |
17 |
Correct |
56 ms |
13496 KB |
Output is correct |
18 |
Correct |
55 ms |
13448 KB |
Output is correct |
19 |
Correct |
79 ms |
13712 KB |
Output is correct |
20 |
Correct |
91 ms |
13812 KB |
Output is correct |
21 |
Correct |
83 ms |
13888 KB |
Output is correct |
22 |
Correct |
77 ms |
13804 KB |
Output is correct |
23 |
Correct |
82 ms |
13668 KB |
Output is correct |
24 |
Correct |
77 ms |
13720 KB |
Output is correct |
25 |
Correct |
79 ms |
13784 KB |
Output is correct |
26 |
Correct |
70 ms |
13648 KB |
Output is correct |
27 |
Correct |
73 ms |
13676 KB |
Output is correct |
28 |
Correct |
71 ms |
13832 KB |
Output is correct |
29 |
Correct |
7 ms |
10892 KB |
Output is correct |
30 |
Correct |
7 ms |
11028 KB |
Output is correct |
31 |
Correct |
9 ms |
11012 KB |
Output is correct |
32 |
Correct |
7 ms |
11060 KB |
Output is correct |
33 |
Correct |
7 ms |
11064 KB |
Output is correct |
34 |
Correct |
7 ms |
11092 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
57 ms |
13344 KB |
Output is correct |
37 |
Correct |
55 ms |
13448 KB |
Output is correct |
38 |
Correct |
105 ms |
13784 KB |
Output is correct |
39 |
Correct |
78 ms |
13860 KB |
Output is correct |
40 |
Correct |
78 ms |
13876 KB |
Output is correct |
41 |
Correct |
7 ms |
11092 KB |
Output is correct |
42 |
Correct |
76 ms |
13732 KB |
Output is correct |
43 |
Correct |
80 ms |
13780 KB |
Output is correct |
44 |
Correct |
86 ms |
13780 KB |
Output is correct |
45 |
Correct |
71 ms |
13728 KB |
Output is correct |
46 |
Correct |
71 ms |
13764 KB |
Output is correct |
47 |
Correct |
70 ms |
13812 KB |
Output is correct |