Submission #977386

#	Time	Username	Problem	Language	Result	Execution time	Memory
977386		sstojilkovic19	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	9172 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;
string aa, bb;
int n = 100010;

vector<vector<int>> pref(7, vector<int>(n, 0)), cnt1(3, vector<int>(n, 0)), cnt2(3, vector<int>(n, 0));

void init(std::string a, std::string b) {
    aa = " " + a;
    bb = " " + b;
    n = a.length();

    /*
    0 uk
    1 AT
    2 TA
    3 AC
    4 CA
    5 TC
    6 CT
    */
    a = " " + a;
    b = " " + b;

    for (int i = 0; i <= 6; i++) {
        for (int j = 1; j <= n; j++) {
            cnt1[0][j] = cnt1[0][j - 1];
            cnt1[1][j] = cnt1[1][j - 1];
            cnt1[2][j] = cnt1[2][j - 1];
            cnt2[0][j] = cnt2[0][j - 1];
            cnt2[1][j] = cnt2[1][j - 1];
            cnt2[2][j] = cnt2[2][j - 1];

            if (a[j] == 'A') cnt1[0][j]++;
            else if (a[j] == 'T') cnt1[1][j]++;
            else cnt1[2][j]++;

            if (b[j] == 'A') cnt2[0][j]++;
            else if (b[j] == 'T') cnt2[1][j]++;
            else cnt2[2][j]++;

            pref[i][j] = pref[i][j - 1];
            if (i == 0 && a[j] != b[j]) pref[i][j]++;
            else if (i == 1 && a[j] == 'A' && b[j] == 'T') pref[i][j]++;
            else if (i == 2 && a[j] == 'T' && b[j] == 'A') pref[i][j]++;
            else if (i == 3 && a[j] == 'A' && b[j] == 'C') pref[i][j]++;
            else if (i == 4 && a[j] == 'C' && b[j] == 'A') pref[i][j]++;
            else if (i == 5 && a[j] == 'T' && b[j] == 'C') pref[i][j]++;
            else if (i == 6 && a[j] == 'C' && b[j] == 'T') pref[i][j]++;
        }
    }
}

int get_distance(int x, int y) {
    x++;
    y++;

    if (cnt1[0][y] - cnt1[0][x - 1] != cnt2[0][y] - cnt2[0][x - 1] ||
        cnt1[1][y] - cnt1[1][x - 1] != cnt2[1][y] - cnt2[1][x - 1] ||
        cnt1[2][y] - cnt1[2][x - 1] != cnt2[2][y] - cnt2[2][x - 1]) {
        return -1;
    }

    int cnt = 0;
    cnt += min(pref[1][y] - pref[1][x - 1], pref[2][y] - pref[2][x - 1]);
    cnt += min(pref[3][y] - pref[3][x - 1], pref[4][y] - pref[4][x - 1]);
    cnt += min(pref[5][y] - pref[5][x - 1], pref[6][y] - pref[6][x - 1]);
    int uk = pref[0][y] - pref[0][x - 1];
    int ans = cnt + 2 * (uk - 2 * cnt) / 3;
    //cout<<cnt<<" "<<uk<<"\n";
    //cout<<pref[0][y]<<" "<<pref[0][x-1]<<"\n";

    return ans;
}

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