Submission #1043806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043806		DeathIsAwe	Mutating DNA (IOI21_dna)	C++17	100 / 100	22 ms	9780 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int pairprefix[100001][9], prefixa[100001][3], prefixb[100001][3];



void init(string a, string b) {
	for (int i=0;i<9;i++) {
		pairprefix[0][i] = 0;
	}
	for (int i=0;i<3;i++) {
		prefixa[0][i] = 0; prefixb[0][i] = 0;
	}
	for (int i=1;i<a.length() + 1;i++) {
		for (int j=0;j<3;j++) {
			prefixa[i][j] = prefixa[i-1][j]; prefixb[i][j] = prefixb[i-1][j];
		}
		for (int j=0;j<9;j++) {
			pairprefix[i][j] = pairprefix[i-1][j];
		}
		if (a[i - 1] == 'A' && b[i - 1] == 'A') {
			prefixa[i][0]++; prefixb[i][0]++;
			pairprefix[i][0]++;
		} else if (a[i - 1] == 'A' && b[i - 1] == 'T') {
			prefixa[i][0]++; prefixb[i][1]++;
			pairprefix[i][1]++;
		} else if (a[i - 1] == 'A' && b[i - 1] == 'C') {
			prefixa[i][0]++; prefixb[i][2]++;
			pairprefix[i][2]++;
		} else if (a[i - 1] == 'T' && b[i - 1] == 'A') {
			prefixa[i][1]++; prefixb[i][0]++;
			pairprefix[i][3]++;
		} else if (a[i - 1] == 'T' && b[i - 1] == 'T') {
			prefixa[i][1]++; prefixb[i][1]++;
			pairprefix[i][4]++;
		} else if (a[i - 1] == 'T' && b[i - 1] == 'C') {
			prefixa[i][1]++; prefixb[i][2]++;
			pairprefix[i][5]++;
		} else if (a[i - 1] == 'C' && b[i - 1] == 'A') {
			prefixa[i][2]++; prefixb[i][0]++;
			pairprefix[i][6]++;
		} else if (a[i - 1] == 'C' && b[i - 1] == 'T') {
			prefixa[i][2]++; prefixb[i][1]++;
			pairprefix[i][7]++;
		} else {
			prefixa[i][2]++; prefixb[i][2]++;
			pairprefix[i][8]++;
		} 
	}
}

int get_distance(int x, int y) {
	for (int i=0;i<3;i++) {
		if (prefixa[y+1][i] - prefixa[x][i] != prefixb[y+1][i] - prefixb[x][i]) {
			return -1;
		}
	}
	

	int ans = 0;
	int AB = pairprefix[y+1][1] - pairprefix[x][1];
	int AC = pairprefix[y+1][2] - pairprefix[x][2];
	int BA = pairprefix[y+1][3] - pairprefix[x][3];
	int BC = pairprefix[y+1][5] - pairprefix[x][5];
	int CA = pairprefix[y+1][6] - pairprefix[x][6];
	int CB = pairprefix[y+1][7] - pairprefix[x][7];


	if (AB > BA) {
		ans += BA;
		AB -= BA; BA = 0; 
	} else {
		ans += AB;
		BA -= AB; AB = 0; 
	}
	if (AC > CA) {
		ans += CA;
		AC -= CA; CA = 0; 
	} else {
		ans += AC;
		CA -= AC; AC = 0; 
	}
	if (BC > CB) {
		ans += CB;
		BC -= CB; CB = 0; 
	} else {
		ans += BC;
		CB -= BC; BC = 0; 
	}
	return ans + 2 * max(AB,BA);
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i=1;i<a.length() + 1;i++) {
      |               ~^~~~~~~~~~~~~~~

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