Submission #867706

#	Time	Username	Problem	Language	Result	Execution time	Memory
867706		_uros9	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	8892 KiB

dna

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

using namespace std;

string a,b;
int n;
vector<int> pa1,pa2,pc1,pc2,pt1,pt2,AC,CA,AT,TA,CT,TC;
void init(std::string aa, std::string bb) {
    a=aa;b=bb;
    n=a.size();
    pa1.resize(n+1,0);pa2.resize(n+1,0);
    pc1.resize(n+1,0);pc2.resize(n+1,0);
    pt1.resize(n+1,0);pt2.resize(n+1,0);
    for(int i=0; i<n; i++){
        pa1[i+1]=pa1[i];pc1[i+1]=pc1[i];pt1[i+1]=pt1[i];
        if(a[i]=='A')
            pa1[i+1]++;
        if(a[i]=='C')
            pc1[i+1]++;
        if(a[i]=='T')
            pt1[i+1]++;
    }
    for(int i=0; i<n; i++){
        pa2[i+1]=pa2[i];pc2[i+1]=pc2[i];pt2[i+1]=pt2[i];
        if(b[i]=='A')
            pa2[i+1]++;
        if(b[i]=='C')
            pc2[i+1]++;
        if(b[i]=='T')
            pt2[i+1]++;
    }
    AC.resize(n+1,0);CA.resize(n+1,0);
    AT.resize(n+1,0);TA.resize(n+1,0);
    CT.resize(n+1,0);TC.resize(n+1,0);
    for(int i=0; i<n; i++){
        AC[i+1]=AC[i];CA[i+1]=CA[i];AT[i+1]=AT[i];TA[i+1]=TA[i];CT[i+1]=CT[i];TC[i+1]=TC[i];
        if(a[i]=='A'&&b[i]=='C')
            AC[i+1]++;
        if(a[i]=='A'&&b[i]=='T')
            AT[i+1]++;
        if(a[i]=='T'&&b[i]=='C')
            TC[i+1]++;
        if(a[i]=='T'&&b[i]=='A')
            TA[i+1]++;
        if(a[i]=='C'&&b[i]=='T')
            CT[i+1]++;
        if(a[i]=='C'&&b[i]=='A')
            CA[i+1]++;
    }
}

int get_distance(int x, int y) {
    y++;
    if(pa1[y]-pa1[x]!=pa2[y]-pa2[x])
        return -1;
    if(pc1[y]-pc1[x]!=pc2[y]-pc2[x])
        return -1;
    if(pt1[y]-pt1[x]!=pt2[y]-pt2[x])
        return -1;
    int A_C=AC[y]-AC[x];
    int A_T=AT[y]-AT[x];
    int C_A=CA[y]-CA[x];
    int C_T=CT[y]-CT[x];
    int T_A=TA[y]-TA[x];
    int T_C=TC[y]-TC[x];
    int rez=0,mini;
    mini=min(A_C,C_A);
    rez+=mini;
    A_C-=mini;
    C_A-=mini;
    mini=min(A_T,T_A);
    rez+=mini;
    A_T-=mini;
    T_A-=mini;
    mini=min(C_T,T_C);
    rez+=mini;
    C_T-=mini;
    T_C-=mini;
    rez+=((A_C+A_T+C_A+C_T+T_A+T_C)/3)*2;
    return rez;
}

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