Submission #806548

#	Time	Username	Problem	Language	Result	Execution time	Memory
806548		AlphaMale06	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	6164 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
int n;
int pref[100010][6]; //0 ab 1 ba 2 ac 3 ca 4 bc 5 cb
void init(std::string a, std::string b) {
    n=a.size();
    for(int i=0; i< n; i++){
        for(int j=0; j< 6; j++)pref[i+1][j]=pref[i][j];
        if(a[i]=='A'){
            if(b[i]=='C'){
                pref[i+1][0]++;
            }
            else if(b[i]=='T'){
                pref[i+1][2]++;
            }
        }
        else if(a[i]=='C'){
            if(b[i]=='A'){
                pref[i+1][1]++;
            }
            else if(b[i]=='T'){
                pref[i+1][4]++;
            }
        }
        else{
            if(b[i]=='A'){
                pref[i+1][3]++;
            }
            else if(b[i]=='C'){
                pref[i+1][5]++;
            }
        }
    }
}

int get_distance(int x, int y) {
	int ab, ba, ac, ca, bc, cb;
	ab=pref[y+1][0]-pref[x][0];
	ba=pref[y+1][1]-pref[x][1];
	ac=pref[y+1][2]-pref[x][2];
	ca=pref[y+1][3]-pref[x][3];
	bc=pref[y+1][4]-pref[x][4];
	cb=pref[y+1][5]-pref[x][5];
	if(ab+ac!=ba+ca || ba+bc !=ab+cb || ca+cb!=ac+bc){
        return -1;
	}
	else{
        int ans=0;
        int ab1=min(ab, ba);
        int ac1=min(ac, ca);
        int bc1=min(bc, cb);
        ans+=ab1+ac1+bc1;
        ab-=ab1; ba-=ab1;
        return ans+max(ab, ba)*2;
	}
}

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