Submission #550518

#	Time	Username	Problem	Language	Result	Execution time	Memory
550518		Zanite	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	8552 KiB

dna

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

const int A = 0, C = 1, T = 2, AC = 0, AT = 1, CA = 2, CT = 3, TA = 4, TC = 5;
const int maxN = 1e5 + 5;
int pref[maxN][6], cha[maxN][3], chb[maxN][3];

void init(string a, string b) {
	a = "#" + a;
	b = "#" + b;
	for (int i = 1; i < a.length(); i++) {
		for (int j = 0; j < 6; j++) {
			pref[i][j] = pref[i-1][j];
		}
		for (int j = 0; j < 3; j++) {
			cha[i][j] = cha[i-1][j];
			chb[i][j] = chb[i-1][j];
		}

		if (a[i] == 'A') {cha[i][A]++;}
		else if (a[i] == 'C') {cha[i][C]++;}
		else {cha[i][T]++;}

		if (b[i] == 'A') {chb[i][A]++;}
		else if (b[i] == 'C') {chb[i][C]++;}
		else {chb[i][T]++;}

		if (a[i] == b[i]) continue;

		if (a[i] == 'A') {
			if (b[i] == 'C') {pref[i][AC]++;}
			else {pref[i][AT]++;}

		} else if (a[i] == 'C') {
			if (b[i] == 'A') {pref[i][CA]++;}
			else {pref[i][CT]++;}

		} else {
			if (b[i] == 'A') {pref[i][TA]++;}
			else {pref[i][TC]++;}
		}
	}
}

int get_distance(int x, int y) {
	int cur[6], cnt[3];
	for (int i = 0; i < 6; i++) {
		cur[i] = pref[y+1][i] - pref[x][i];
	}
	for (int i = 0; i < 3; i++) {
		cnt[i] = (cha[y+1][i] - cha[x][i]) - (chb[y+1][i] - chb[x][i]);
		if (cnt[i] != 0) return -1;
	}

	int ans = 0;
	
	int m1 = min(cur[AC], cur[CA]);
	ans += m1;
	cur[AC] -= m1;
	cur[CA] -= m1;

	int m2 = min(cur[AT], cur[TA]);
	ans += m2;
	cur[AT] -= m2;
	cur[TA] -= m2;

	int m3 = min(cur[CT], cur[TC]);
	ans += m3;
	cur[CT] -= m3;
	cur[TC] -= m3;

	// {AT} {TC} {CA}
	//assert((cur[AT] == cur[TC]) && (cur[TC] == cur[CA]));
	ans += (cur[AT] << 1);

	// {AC} {CT} {TA}
	//assert((cur[AC] == cur[CT]) && (cur[CT] == cur[TA]));
	ans += (cur[AC] << 1);

	return ans;
}

Compilation message (stderr)

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

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