Submission #548545

#	Time	Username	Problem	Language	Result	Execution time	Memory
548545		Clan328	Mutating DNA (IOI21_dna)	C++17	100 / 100	290 ms	88636 KiB

dna

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

using namespace std;

string a, b;
vector<map<pair<char, char>, int>> link;
vector<map<char, int>> dp1, dp2;

void init(std::string A, std::string B) {
	a = A;
	b = B;
	dp1 = vector<map<char, int>>(a.size());
	dp2 = vector<map<char, int>>(a.size());
	link = vector<map<pair<char, char>, int>>(a.size());

	for (int i = 0; i < a.size(); i++) {
		if (i > 0) {
			dp1[i] = dp1[i-1];
			dp2[i] = dp2[i-1];

			link[i] = link[i-1];
		}
		
		dp1[i][a[i]]++;
		dp2[i][b[i]]++;

		link[i][{a[i], b[i]}]++;
	}
}

int get_distance(int x, int y) {
	if (x != 0) {
		if (!(
			dp1[y]['A']-dp1[x-1]['A'] == dp2[y]['A']-dp2[x-1]['A'] && 
			dp1[y]['C']-dp1[x-1]['C'] == dp2[y]['C']-dp2[x-1]['C'] &&
			dp1[y]['T']-dp1[x-1]['T'] == dp2[y]['T']-dp2[x-1]['T']
			))
				return -1;
	} else {
		if (!(
			dp1[y]['A'] == dp2[y]['A'] && 
			dp1[y]['C'] == dp2[y]['C'] &&
			dp1[y]['T'] == dp2[y]['T']
			)) return -1;
	}

	int AC = link[y][{'A', 'C'}] - (x > 0? link[x-1][{'A', 'C'}] : 0);
	int CA = link[y][{'C', 'A'}] - (x > 0? link[x-1][{'C', 'A'}] : 0);
	int CT = link[y][{'C', 'T'}] - (x > 0? link[x-1][{'C', 'T'}] : 0);
	int TC = link[y][{'T', 'C'}] - (x > 0? link[x-1][{'T', 'C'}] : 0);
	int AT = link[y][{'A', 'T'}] - (x > 0? link[x-1][{'A', 'T'}] : 0);
	int TA = link[y][{'T', 'A'}] - (x > 0? link[x-1][{'T', 'A'}] : 0);

	int res = 0;

	res += min(AC, CA)+min(CT, TC)+min(AT, TA);

	int tmp = min(AC, CA);
	AC -= tmp;
	CA -= tmp;
	tmp = min(AT, TA);
	AT -= tmp;
	TA -= tmp;
	tmp = min(CT, TC);
	CT -= tmp;
	TC -= tmp;

	if (AC+CA+AT+TA+CT+TC != 0) {
		res += 2*(AC+CA+AT+TA+CT+TC)/3;
	} else
		res += (AC+CA+AT+TA+CT+TC)/2;

	return res;
}

Compilation message (stderr)

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

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