Submission #991311

#	Time	Username	Problem	Language	Result	Execution time	Memory
991311		SpyrosAliv	Mutating DNA (IOI21_dna)	C++17	56 / 100	27 ms	6176 KiB

dna

#include <bits/stdc++.h>
using namespace std;

vector<int> cntAA, cntTA, cntCA;
vector<int> cntAB, cntTB, cntCB;
vector<int> diffs;
int n;


void init(string a, string b) {
    n = a.size();
    cntAA.assign(n, 0), cntTA.assign(n, 0), cntCA.assign(n, 0);
    cntAB.assign(n, 0), cntTB.assign(n, 0), cntCB.assign(n, 0);
    for (int i = 0; i < n; i++) {
        if (a[i] == 'A') cntAA[i]++;
        else if (a[i] == 'T') cntTA[i]++;
        else cntCA[i]++;
        if (b[i] == 'A') cntAB[i]++;
        else if (b[i] == 'C') cntCB[i]++;
        else cntTB[i]++;
    }
    diffs.assign(n, 0);
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) diffs[i]++;
    }
    for (int i = 1; i < n; i++) {
        diffs[i] += diffs[i-1];
        cntAA[i] += cntAA[i-1];
        cntCA[i] += cntCA[i-1];
        cntTA[i] += cntTA[i-1];
        cntAB[i] += cntAB[i-1];
        cntCB[i] += cntCB[i-1];
        cntTB[i] += cntTB[i-1];
    }
}

int get_distance(int x, int y) {
    if (x == 0) {
        if (cntAA[y] != cntAB[y]
        || cntCA[y] != cntCB[y]
        || cntTA[y] != cntTB[y]) return -1;
    }
    else {
        if (cntAA[y] - cntAA[x-1] != cntAB[y] - cntAB[x-1]
        || cntCA[y] - cntCA[x-1] != cntCB[y] - cntCB[x-1]
        || cntTA[y] - cntTA[x-1] != cntTB[y] - cntTB[x-1]) return -1;
    }
    if (x == 0) {
        return diffs[y] / 2 + (diffs[y] % 2);
    }
    else {
        int k = diffs[y] - diffs[x-1];
        return k / 2 + (k % 2);
    }
}
/*
int main() {
    init("ATACAT", "ACTATA");
    cout << get_distance(1, 3) << "\n" << get_distance(4, 5) << "\n" << get_distance(3, 5) << "\n";
    return 0;

}*/

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