Submission #998810

#	Time	Username	Problem	Language	Result	Execution time	Memory
998810		spensa	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	6168 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
typedef long long ll;

const int MXN = 1e5 +10;
int ac[MXN] = {0};
int ca[MXN] = {0};
int at[MXN] = {0};
int ta[MXN] = {0};
int ct[MXN] = {0};
int tc[MXN] = {0};

int N;
void init(std::string a, std::string b) {
    N = a.length();
    for(int i=0; i<N; i++){
        if(i!=0){
            ac[i] = ac[i-1];
            ca[i] = ca[i-1];
            at[i] = at[i-1];
            ta[i] = ta[i-1];
            ct[i] = ct[i-1];
            tc[i] = tc[i-1];
        }

        if(a[i]=='A' && b[i]=='C') ac[i]++;
        if(a[i]=='C' && b[i]=='A') ca[i]++;
        if(a[i]=='A' && b[i]=='T') at[i]++;
        if(a[i]=='T' && b[i]=='A') ta[i]++;
        if(a[i]=='C' && b[i]=='T') ct[i]++;
        if(a[i]=='T' && b[i]=='C') tc[i]++;
    }

    // for(int i=0; i<N; i++) cout<<ca[i]<<" ";
    // cout<<"\n";
}


int get_distance(int x, int y) {
    ll tac, tca, tat, tta, tct, ttc;
    tac = ac[y]; tca = ca[y]; tat = at[y];
    tta = ta[y]; tct = ct[y]; ttc = tc[y];
    if(x!=0){
        tac -= ac[x-1]; tca -= ca[x-1]; tat -= at[x-1];
        tta -= ta[x-1]; tct -= ct[x-1]; ttc -= tc[x-1];            
    }

    ll ans = 0LL;
    ans += (min(tac,tca) + min(tat,tta) + min(tct,ttc));
    ll t1, t2, t3;

    if(tac<tca){
        tca -= tac;
        tac = 0;
        t1 = tca;
    }
    else{
        tac -= tca;
        tca = 0;
        t1 = tac;
    }

    if(tat<tta){
        tta -= tat;
        tat = 0;
        t2 = tta;
    }
    else{
        tat -= tta;
        tta = 0;
        t2 = tat;
    }

    if(tct<ttc){
        ttc -= tct;
        tct = 0;
        t3 = ttc;
    }
    else{
        tct -= ttc;
        ttc = 0;
        t3 = tct;
    }

    // cout<<"t1="<<t1<<" t2="<<t2<<" t3="<<t3<<"\n";
    if(!((t1==t2) && (t2==t3))) return -1;

    if((t1==tac && t2==tct && t3==tta) || (t1==tca && t2==ttc && t3==tat)){
        ans += (t1*2);
        return ans;
    }

    return -1;

}

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