Submission #605399

#	Time	Username	Problem	Language	Result	Execution time	Memory
605399		Tigerpants	Mutating DNA (IOI21_dna)	C++17	100 / 100	1395 ms	51148 KiB

dna

#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 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16