Submission #591917

#	Time	Username	Problem	Language	Result	Execution time	Memory
591917		Jarif_Rahman	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	7408 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<int> A, T, C, AT, CT, AC, TC, CA, TA;

void init(str a, str b){
    int n = a.size();
    A.assign(n, 0);
    T.assign(n, 0);
    C.assign(n, 0);
    AT.assign(n, 0);
    CT.assign(n, 0);
    AC.assign(n, 0);
    TC.assign(n, 0);
    CA.assign(n, 0);
    TA.assign(n, 0);

    for(int i = 0; i < n; i++){
        if(i != 0) A[i] = A[i-1], T[i] = T[i-1], C[i] = C[i-1];
        if(a[i] == 'A') A[i]++;
        if(a[i] == 'T') T[i]++;
        if(a[i] == 'C') C[i]++;
        if(b[i] == 'A') A[i]--;
        if(b[i] == 'T') T[i]--;
        if(b[i] == 'C') C[i]--;
    }

    for(int i = 0; i < n; i++){
        if(i != 0)
            AT[i] = AT[i-1], CT[i] = CT[i-1],
            AC[i] = AC[i-1], TC[i] = TC[i-1],
            CA[i] = CA[i-1], TA[i] = TA[i-1];
        if(a[i] == 'A' && b[i]  == 'T') AT[i]++;
        if(a[i] == 'C' && b[i]  == 'T') CT[i]++;
        if(a[i] == 'A' && b[i]  == 'C') AC[i]++;
        if(a[i] == 'T' && b[i]  == 'C') TC[i]++;
        if(a[i] == 'C' && b[i]  == 'A') CA[i]++;
        if(a[i] == 'T' && b[i]  == 'A') TA[i]++;
    }
}

int getsum(int l, int r, vector<int> &v){
    return v[r]-(l == 0 ? 0: v[l-1]);
}

int getmn(int &a, int &b){
    int mn = min(a, b);
    a-=mn, b-=mn;
    return mn;
}

int get_distance(int l, int r){
    if(getsum(l, r, A) != 0 || getsum(l, r, C) != 0 || getsum(l, r, T) != 0) return -1;

    int at = getsum(l, r, AT), ct = getsum(l, r, CT);
    int ac = getsum(l, r, AC), tc = getsum(l, r, TC);
    int ca = getsum(l, r, CA), ta = getsum(l, r, TA);

    int ans = 0;
    ans+=getmn(at, ta);
    ans+=getmn(ct, tc);
    ans+=getmn(ac, ca);

    if(at != 0) ans+=at+tc+ca-min(at, min(tc, ca));
    else ans+=ta+ac+ct-min(ta, min(ac, ct));

    return ans;
}

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