Submission #437367

#	Time	Username	Problem	Language	Result	Execution time	Memory
437367		Gabp	Mutating DNA (IOI21_dna)	C++17	100 / 100	76 ms	6192 KiB

dna

#include "dna.h"

const int N = 1e5 + 5;
int cnt[3][3][N];

void init(std::string a, std::string b) {
	int n = a.size();
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cnt[i][j][0] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		int first,second;
		switch (a[i]) {
			case 'A': first = 0; break;
			case 'C': first = 1; break;
			case 'T': first = 2;
		}
		switch (b[i]) {
			case 'A': second = 0; break;
			case 'C': second = 1; break;
			case 'T': second = 2;
		}

		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				cnt[j][k][i + 1] = cnt[j][k][i];
				if (j == first && k == second)
					cnt[j][k][i + 1]++;
			}
		}
	}
}

int get_distance(int x, int y) {
	int curr[3][3];

	for (int i = 0; i < 3; i++) {
		int compare1 = 0, compare2 = 0;
		for (int j = 0; j < 3; j++) {
			curr[i][j] = cnt[i][j][y + 1] - cnt[i][j][x];
			compare1 += cnt[i][j][y + 1] - cnt[i][j][x];
			compare2 += cnt[j][i][y + 1] - cnt[j][i][x];
		}
		if (compare1 != compare2)
			return -1;
	}

	int ans = 0;
	int extra = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = i + 1; j < 3; j++) {
			int temp = std::min(curr[i][j], curr[j][i]);
			ans += temp;
			curr[i][j] -= temp;
			curr[j][i] -= temp;
			extra += curr[i][j] + curr[j][i];
		}
	}
	ans += extra / 3 * 2;

	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:29:25: warning: 'second' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     if (j == first && k == second)
      |                       ~~^~~~~~~~~
dna.cpp:29:11: warning: 'first' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     if (j == first && k == second)
      |         ~~^~~~~~~~

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