Submission #437041

#	Time	Username	Problem	Language	Result	Execution time	Memory
437041		Elegia	Mutating DNA (IOI21_dna)	C++17	100 / 100	48 ms	6060 KiB

dna

#include "dna.h"

#include <vector>

int n;
std::vector<int> cnt[3][3];

int mp[256];

void init(std::string a, std::string b) {
	mp['A'] = 0; mp['T'] = 1; mp['C'] = 2;
	n = a.length();
	for (int i = 0; i != 3; ++i) for (int j = 0; j != 3; ++j)
		cnt[i][j].resize(n + 1);
	for (int i = 0; i != n; ++i) {
		int u = mp[a[i]], v = mp[b[i]];
		for (int j = 0; j != 3; ++j)
			for (int k = 0; k != 3; ++k)
				cnt[j][k][i + 1] = cnt[j][k][i] + (j == u && k == v);
	}
}

int get_distance(int x, int y) {
	int ans = 0, cyc = -1;
	for (int i = 0; i != 3; ++i) {
		int j = (i + 1) % 3;
		int a = cnt[i][j][y + 1] - cnt[i][j][x],
		    b = cnt[j][i][y + 1] - cnt[j][i][x];
		if (i == 0) cyc = a - b;
		else if (cyc != a - b) return -1;
		ans += std::min(a, b);
	}
	return ans + abs(cyc) * 2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:16:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |   int u = mp[a[i]], v = mp[b[i]];
      |                  ^
dna.cpp:16:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |   int u = mp[a[i]], v = mp[b[i]];
      |                                ^

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