oj.uz

Submission #605399

# Submission time Handle Problem Language Result Execution time Memory
605399 2022-07-25T17:06:17 Z Tigerpants Mutating DNA (IOI21_dna) C++17
100 / 100
 1395 ms 51148 KB 
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>

using namespace std;

typedef vector<vector<int>> int33;

map<char, int> get_index;
map<int, char> get_char;

int n;

vector<pair<int, int>> segtree_span;
vector<int33> segtree;

vector<char> origin;
vector<char> mutated;

int33 calculate_crossmultiply(int index) {
    int33 result{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    result[get_index[origin[index]]][get_index[mutated[index]]] = 1;
    return result;
}

int33 combine(int33 a, int33 b) {
    int33 result{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result[i][j] = a[i][j] + b[i][j];
        }
    }
    return result;
}

void build(int x, int l, int r) {
    segtree_span[x] = make_pair(l, r);

    if (l == r) {
        segtree[x] = calculate_crossmultiply(l);
        return;
    }

    int mid = (l + r) / 2;

    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    segtree[x] = combine(segtree[2 * x], segtree[2 * x + 1]);
}

int33 query(int x, int l, int r) {
    if ((segtree_span[x].first > r) || (segtree_span[x].second < l)) {
        int33 result{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
        return result;
    }

    if ((segtree_span[x].first >= l) && (segtree_span[x].second <= r)) {
        return segtree[x];
    }

    return combine(query(2 * x, l, r), query(2 * x + 1, l, r));
}

void init(string a, string b) {
    // initialize maps between amino acids and indices
    get_index['A'] = 0; get_index['C'] = 1; get_index['T'] = 2;
    get_char[0] = 'A'; get_char[1] = 'C'; get_char[2] = 'T';

    // take in the data
    n = a.size();
    origin.resize(n);
    mutated.resize(n);

    for (int i = 0; i < n; i++) {
        origin[i] = a[i];
        mutated[i] = b[i];
    }

    // construct the segment tree
    segtree_span.resize(4 * n);
    segtree.resize(4 * n);

    build(1, 0, n - 1);
}

int get_distance(int x, int y) {
    int33 cross = query(1, x, y);
    int distance = 0;
    int result;

    // check if it is possible to begin with:
    bool possible = true;
    for (int i = 0; i < 3; i++) {
        possible &= (cross[i][0] + cross[i][1] + cross[i][2] == cross[0][i] + cross[1][i] + cross[2][i]);
    }

    if (!possible) {
        return -1;
    }

    // go into all cases ig:

    // (a, b) - (b, a) --> (a, a) - (b, b)
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < i; j++) {
            result = min<int>(cross[i][j], cross[j][i]);
            distance += result;
            cross[i][j] -= result;
            cross[j][i] -= result;
        }
    }

    // (a, b) - (b, c) - (c, a) --> (a, a) - (b, b) - (c, c) in 2 moves
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if ((i != j) && (j != k) && (k != i)) {
                    result = min<int>(cross[i][j], min<int>(cross[j][k], cross[k][i]));
                    distance += 2 * result;
                    cross[i][j] -= result;
                    cross[j][k] -= result;
                    cross[k][i] -= result;
                }
            }
        }
    }

    return distance;

}

/*
int main() {
    return 0;
}
*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 50092 KB Output is correct
2 Correct 869 ms 50692 KB Output is correct
3 Correct 856 ms 46464 KB Output is correct
4 Correct 906 ms 50696 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 137 ms 47656 KB Output is correct
5 Correct 116 ms 48256 KB Output is correct
6 Correct 117 ms 47920 KB Output is correct
7 Correct 118 ms 44876 KB Output is correct
8 Correct 131 ms 48192 KB Output is correct
9 Correct 117 ms 48144 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 137 ms 47656 KB Output is correct
5 Correct 116 ms 48256 KB Output is correct
6 Correct 117 ms 47920 KB Output is correct
7 Correct 118 ms 44876 KB Output is correct
8 Correct 131 ms 48192 KB Output is correct
9 Correct 117 ms 48144 KB Output is correct
10 Correct 957 ms 50104 KB Output is correct
11 Correct 836 ms 50692 KB Output is correct
12 Correct 1350 ms 47756 KB Output is correct
13 Correct 1352 ms 48936 KB Output is correct
14 Correct 1332 ms 51100 KB Output is correct
15 Correct 1395 ms 50944 KB Output is correct
16 Correct 1222 ms 47800 KB Output is correct
17 Correct 1201 ms 48856 KB Output is correct
18 Correct 1211 ms 50984 KB Output is correct
19 Correct 1128 ms 47656 KB Output is correct
20 Correct 1126 ms 48836 KB Output is correct
21 Correct 1134 ms 50964 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 137 ms 47656 KB Output is correct
5 Correct 116 ms 48256 KB Output is correct
6 Correct 117 ms 47920 KB Output is correct
7 Correct 118 ms 44876 KB Output is correct
8 Correct 131 ms 48192 KB Output is correct
9 Correct 117 ms 48144 KB Output is correct
10 Correct 116 ms 44168 KB Output is correct
11 Correct 113 ms 48200 KB Output is correct
12 Correct 106 ms 45040 KB Output is correct
13 Correct 114 ms 47824 KB Output is correct
14 Correct 114 ms 48248 KB Output is correct
15 Correct 112 ms 48160 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 50092 KB Output is correct
2 Correct 869 ms 50692 KB Output is correct
3 Correct 856 ms 46464 KB Output is correct
4 Correct 906 ms 50696 KB Output is correct
5 Correct 1 ms 304 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 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 137 ms 47656 KB Output is correct
12 Correct 116 ms 48256 KB Output is correct
13 Correct 117 ms 47920 KB Output is correct
14 Correct 118 ms 44876 KB Output is correct
15 Correct 131 ms 48192 KB Output is correct
16 Correct 117 ms 48144 KB Output is correct
17 Correct 957 ms 50104 KB Output is correct
18 Correct 836 ms 50692 KB Output is correct
19 Correct 1350 ms 47756 KB Output is correct
20 Correct 1352 ms 48936 KB Output is correct
21 Correct 1332 ms 51100 KB Output is correct
22 Correct 1395 ms 50944 KB Output is correct
23 Correct 1222 ms 47800 KB Output is correct
24 Correct 1201 ms 48856 KB Output is correct
25 Correct 1211 ms 50984 KB Output is correct
26 Correct 1128 ms 47656 KB Output is correct
27 Correct 1126 ms 48836 KB Output is correct
28 Correct 1134 ms 50964 KB Output is correct
29 Correct 116 ms 44168 KB Output is correct
30 Correct 113 ms 48200 KB Output is correct
31 Correct 106 ms 45040 KB Output is correct
32 Correct 114 ms 47824 KB Output is correct
33 Correct 114 ms 48248 KB Output is correct
34 Correct 112 ms 48160 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 772 ms 46460 KB Output is correct
37 Correct 799 ms 50692 KB Output is correct
38 Correct 1286 ms 48152 KB Output is correct
39 Correct 1336 ms 51076 KB Output is correct
40 Correct 1293 ms 51148 KB Output is correct
41 Correct 109 ms 48264 KB Output is correct
42 Correct 1191 ms 48120 KB Output is correct
43 Correct 1209 ms 50968 KB Output is correct
44 Correct 1235 ms 50992 KB Output is correct
45 Correct 1113 ms 48028 KB Output is correct
46 Correct 1114 ms 50968 KB Output is correct
47 Correct 1131 ms 50972 KB Output is correct