Submission #625332

#	Time	Username	Problem	Language	Result	Execution time	Memory
625332		moyindavid	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	6192 KiB

dna

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

using namespace std;
int AT[100000],TA[100000],AC[100000],CA[100000],TC[100000],CT[100000];


void init(string a, string b) {
    AT[0]=TA[0]=AC[0]=CA[0]=TC[0]=CT[0]=0;
    int n=a.size();
    for(int i=0;i<n;i++){
        if(i!=0){
            AT[i]=AT[i-1];TA[i]=TA[i-1];AC[i]=AC[i-1];CA[i]=CA[i-1];TC[i]=TC[i-1];CT[i]=CT[i-1];
        }

        if(a[i]=='A'&&b[i]=='T')AT[i]++;
        else if(a[i]=='T'&&b[i]=='A')TA[i]++;
        else if(a[i]=='A'&&b[i]=='C')AC[i]++;
        else if(a[i]=='C'&&b[i]=='A')CA[i]++;
        else if(a[i]=='T'&&b[i]=='C')TC[i]++;
        else if(a[i]=='C'&&b[i]=='T')CT[i]++;
    }
}

int get_distance(int x, int y) {
    int ans=0;
    if(x==0){
        ans+=min(TA[y],AT[y])+min(AC[y],CA[y])+min(TC[y],CT[y]);
        int rem=abs(TA[y]-(AT[y]))+abs(AC[y]-(CA[y]))+abs(TC[y]-(CT[y]));
        if(rem%3!=0 || TA[y]+TC[y] != AT[y]+CT[y] || AT[y]+AC[y] != TA[y]+CA[y] || CA[y]+CT[y] != AC[y]+TC[y])return -1;
        ans+=(rem/3)*2;
        return ans;

    }
    x--;
    ans+=min(TA[y]-TA[x],AT[y]-AT[x])+min(AC[y]-AC[x],CA[y]-CA[x])+min(TC[y]-TC[x],CT[y]-CT[x]);
    int rem=abs(TA[y]-TA[x]-(AT[y]-AT[x]))+abs(AC[y]-AC[x]-(CA[y]-CA[x]))+abs(TC[y]-TC[x]-(CT[y]-CT[x]));
    if(rem%3!=0 || TA[y]-TA[x]+TC[y]-TC[x] != AT[y]-AT[x]+CT[y]-CT[x] || AT[y]-AT[x]+AC[y]-AC[x] != TA[y]-TA[x]+CA[y]-CA[x] || CA[y]-CA[x]+CT[y]-CT[x] != AC[y]-AC[x]+TC[y]-TC[x])return -1;
    ans+=(rem/3)*2;
	return ans;
}

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