Submission #840825

#	Time	Username	Problem	Language	Result	Execution time	Memory
840825		Jkap	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	7792 KiB

dna

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

#define ll long long
#define vl vector<ll>
#define for1(i, n) for (ll i=0; i<n; i++)

int nA1[100005], nA2[100005], nC1[100005], nC2[100005], AT[100005], AC[100005], CT[100005], CA[100005], TC[100005], TA[100005];

void init(string a, string b) {
    ll n = a.size();
    for1(i, n) {
        nA1[i+1] = nA1[i];
        nC1[i+1] = nC1[i];
        nA2[i+1] = nA2[i];
        nC2[i+1] = nC2[i];
        AT[i+1] = AT[i];
        AC[i+1] = AC[i];
        CT[i+1] = CT[i];
        CA[i+1] = CA[i];
        TA[i+1] = TA[i];
        TC[i+1] = TC[i];
        if (a[i] == 'A') {
            nA1[i+1]++;
            if (b[i] == 'C') {
                AC[i+1] ++;
            }
            if (b[i] == 'T') {
                AT[i+1] ++;
            }
        }
        else if (a[i] == 'C') {
            nC1[i+1] ++;
            if (b[i] == 'A') {
                CA[i+1] ++;
            }
            if (b[i] == 'T') {
                CT[i+1] ++;
            }
        }
        else {
            if (b[i] == 'C') {
                TC[i+1] ++;
            }
            if (b[i] == 'A') {
                TA[i+1] ++;
            }
        }
        if (b[i] == 'A') {
            nA2[i+1]++;
        }
        else if (b[i] == 'C') {
            nC2[i+1] ++;
        }
    }
}

int get_distance(int x, int y) {
    if (nA1[y+1] - nA1[x] != nA2[y+1] - nA2[x] || nC1[y+1] - nC1[x] != nC2[y+1] - nC2[x]) {
        return -1;
    }
    int out;
    out = min(AC[y+1]-AC[x], CA[y+1]-CA[x]);
    out += min(AT[y+1]-AT[x], TA[y+1]-TA[x]);
    out += min(TC[y+1]-TC[x], CT[y+1]-CT[x]);
    out += 2*(max(AC[y+1]-AC[x], CA[y+1]-CA[x]) - min(AC[y+1]-AC[x], CA[y+1]-CA[x]));
    return out;
}

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