Submission #616082

#	Time	Username	Problem	Language	Result	Execution time	Memory
616082		sokratisi	Mutating DNA (IOI21_dna)	C++17	100 / 100	143 ms	18284 KiB

dna

#include "dna.h"
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> st;
int k;

void addv(vector<int>& re, vector<int> a) {
    for (int i = 0; i < 6; i++) re[i] += a[i];
}

vector<int> range(int x, int y) {
    vector<int> re(6, 0);
    x += k; y += k;
    while (x <= y) {
        if (x % 2) addv(re, st[x++]);
        if (!(y % 2)) addv(re, st[y--]);
        x /= 2; y /= 2;
    }
    return re;
}

int calculate_ans(vector<int> a) {
    if (a[0] - a[3] == a[1] - a[4] && a[1] - a[4] == a[2] - a[5]) {
        int ans;
        if (a[0] < a[3]) {
            ans = a[0] + a[1] + a[2] + 2 * (a[3] - a[0]);
        }
        else {
            ans = a[3] + a[4] + a[5] + 2 * (a[0] - a[3]);
        }
        return ans;
    }
    return -1;
}

void init(string a, string b) {
    int n = a.size();
    k = 1;
    while (k < n) k *= 2;
    st.resize(2*k, vector<int>(6, 0));
    for (int i = 0; i < n; i++) {
        if (a[i] == 'A') {
            if (b[i] == 'C') {
                st[i + k][0] = 1;
            }
            else if (b[i] == 'T') {
                st[i + k][5] = 1;
            }
        }
        else if (a[i] == 'C') {
            if (b[i] == 'A') {
                st[i + k][3] = 1;
            }
            else if (b[i] == 'T') {
                st[i + k][1] = 1;
            }
        }
        else {
            if (b[i] == 'A') {
                st[i + k][2] = 1;
            }
            else if (b[i] == 'C') {
                st[i + k][4] = 1;
            }
        }
    }
    for (int i = k - 1; i > 0; i--) {
        for (int j = 0; j < 6; j++) {
            st[i][j] += st[2*i][j];
            st[i][j] += st[2*i+1][j];
        }
    }
    // for (int i = 1; i < 2 * k; i++) {
    //     cout << "[";
    //     for (int j = 0; j < 5; j++) {
    //         cout << st[i][j] << ", ";
    //     }
    //     cout << st[i][5] << "]\n";
    // }
}

int get_distance(int x, int y) {
	vector<int> use = range(x, y);
    return calculate_ans(use);
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16