Submission #1004823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004823		chimene	Mutating DNA (IOI21_dna)	C++17	100 / 100	27 ms	6424 KiB

dna

#include "dna.h"

#include<bits/stdc++.h>
using namespace std;

int cumu[6][100*1000];
int achanger[6];
string mota,motb;

void init(std::string a, std::string b) {
	int n=a.size();
	for (int i=0;i<n;i++){
		if (a[i]!=b[i]){
			if (a[i]=='A' and b[i]=='C'){
				cumu[0][i]++;
			}
			else if (a[i]=='A' and b[i]=='T'){
				cumu[1][i]++;
			}
			else if (a[i]=='C' and b[i]=='A'){
				cumu[2][i]++;
			}
			else if (a[i]=='C' and b[i]=='T'){
				cumu[3][i]++;
			}
			else if (a[i]=='T' and b[i]=='A'){
				cumu[4][i]++;
			}
			else{
				cumu[5][i]++;
			}
		}
	}
	for (int it=0;it<6;it++){
		for (int i=1;i<n;i++){
			cumu[it][i]+=cumu[it][i-1];
		}
	}
}

int get_distance(int x, int y) {
	int rep=0,nbdiffAa,nbdiffCa,nbdiffTa,nbdiffAb,nbdiffCb,nbdiffTb=0,temp=0;
	for (int it=0;it<6;it++){
		achanger[it]=cumu[it][y];
		if (x>0){
			achanger[it]-=cumu[it][x-1];
		}
	}
	nbdiffAa=achanger[0]+achanger[1];
	nbdiffCa=achanger[2]+achanger[3];
	nbdiffTa=achanger[4]+achanger[5];
	nbdiffAb=achanger[2]+achanger[4];
	nbdiffCb=achanger[0]+achanger[5];
	nbdiffTb=achanger[1]+achanger[3];
	if (nbdiffAa!=nbdiffAb or nbdiffCa!=nbdiffCb or nbdiffTa!=nbdiffTb){
		return -1;
	}
	if (achanger[0]>=achanger[2]){
		rep+=achanger[2];
		achanger[0]-=achanger[2];
		achanger[2]=0;
	}
	else{
		rep+=achanger[0];
		achanger[2]-=achanger[0];
		achanger[0]=0;
	}
	if (achanger[1]>=achanger[4]){
		rep+=achanger[4];
		achanger[1]-=achanger[4];
		achanger[4]=0;
	}
	else{
		rep+=achanger[1];
		achanger[4]-=achanger[1];
		achanger[1]=0;
	}
	if (achanger[3]>=achanger[5]){
		rep+=achanger[5];
		achanger[3]-=achanger[5];
		achanger[5]=0;
	}
	else{
		rep+=achanger[3];
		achanger[5]-=achanger[3];
		achanger[3]=0;
	}
	for (int it=0;it<6;it++){
		temp+=2*achanger[it];
	}
	temp/=3;
	rep+=temp;
	return rep;
}

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