Submission #523209

#	Time	Username	Problem	Language	Result	Execution time	Memory
523209		marat0210	Mutating DNA (IOI21_dna)	C++17	100 / 100	64 ms	23516 KiB

dna

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

using namespace std;

const int N = 500500;

vector <int> aaa(N), aat(N), aac(N), bba(N), bbt(N), bbc(N), at(N), ta(N), ct(N), ax(N);

vector <int> posa, posb;

void init(string a, string b)
{
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        aaa[i + 1] = aaa[i];
        aat[i + 1] = aat[i];
        aac[i + 1] = aac[i];
        bba[i + 1] = bba[i];
        bbt[i + 1] = bbt[i];
        bbc[i + 1] = bbc[i];
        at[i + 1] = at[i];
        ta[i + 1] = ta[i];
        ct[i + 1] = ct[i];
        ax[i + 1] = ax[i];
        if (a[i] == 'A') {
            aaa[i + 1]++;
        }
        else if (a[i] == 'T') {
            aat[i + 1]++;
        }
        else if (a[i] == 'C') {
            aac[i + 1]++;
        }
        if (b[i] == 'A') {
            bba[i + 1]++;
        }
        else if (b[i] == 'T') {
            bbt[i + 1]++;
        }
        else if (b[i] == 'C') {
            bbc[i + 1]++;
        }
        if (a[i] == 'A' and b[i] == 'T') {
            at[i + 1]++;
        }
        if (a[i] == 'T' and b[i] == 'A') {
            ta[i + 1]++;
        }
        if (a[i] == 'C' and b[i] == 'T') {
            ct[i + 1]++;
        }
        if (a[i] == 'T' and b[i] == 'C') {
            ct[i + 1]++;
        }
        if (a[i] == 'A' and b[i] != 'A') {
            ax[i + 1]++;
        }
    }
}

int get_distance(int x, int y)
{
    x++;
    y++;
    int diff = ax[y] - ax[x - 1];
    int cnta = at[y] - at[x - 1];
    int cntt = ta[y] - ta[x - 1];
    int cntc = ct[y] - ct[x - 1];
    if (aaa[y] - aaa[x - 1] != bba[y] - bba[x - 1] or aat[y] - aat[x - 1] != bbt[y] - bbt[x - 1] or aac[y] - aac[x - 1] != bbc[y] - bbc[x - 1]) {
        return -1;
    }
    else {
        int res = diff + (cntc + abs((cnta - cntt))) / 2;
        return res;
    }
}

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