Submission #437361

#	Time	Username	Problem	Language	Result	Execution time	Memory
437361		m_bezrutchka	Mutating DNA (IOI21_dna)	C++17	100 / 100	70 ms	9508 KiB

dna

#include "dna.h"
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 112345;

int char_to_int(char c) {
	if (c == 'A') return 0;
	if (c == 'C') return 1;
	return 2;
}

char int_to_char(int x) {
	if (x == 0) return 'A';
	if (x == 1) return 'C';
	return 'T';
}

int occur[2][3][MAXN];
int diff[MAXN];
int tot_pairs[3][3][MAXN];
int n;

void init(string a, string b) {
	// printf("%s\n%s\n", a.c_str(), b.c_str());
	// printf("init started\n");
	n = (int) a.size();
	for (int i = 1; i <= n; i++) {
		for (int k = 0; k < 3; k++) {
			occur[0][k][i] = occur[0][k][i - 1];
			occur[1][k][i] = occur[1][k][i - 1];
			for (int r = 0; r < 3; r++) {
				for (int s = 0; s < 3; s++) {
					tot_pairs[r][s][i] = tot_pairs[r][s][i - 1];
				}
			}
		}

		int val_a = char_to_int(a[i - 1]);
		occur[0][val_a][i]++;

		int val_b = char_to_int(b[i - 1]);
		occur[1][val_b][i]++;

		tot_pairs[val_a][val_b][i]++;

		if (val_a != val_b) {
			diff[i] = diff[i - 1] + 1;
		} else {
			diff[i] = diff[i - 1];
		}
	}
	/* printf("init finished\n");

	printf("occur:\n");
	for (int s = 0; s < 2; s++) {
		for (int k = 0; k < 3; k++) {
			printf("%d %c: ", s, int_to_char(k));
			for (int i = 1; i <= n; i++) {
				printf("%d ", occur[s][k][i]);
			}
			printf("\n");
		}
	}

	printf("diff:\n");
	for (int i = 1; i <= n; i++) {
		printf("%d ", diff[i]);
	}
	printf("\n");

	printf("tot_pairs:\n");
	for (int i = 1; i <= n; i++) {
		printf("i = %d\n", i);
		printf("  %c %c %c\n", int_to_char(0), int_to_char(1), int_to_char(2));
		for (int r = 0; r < 3; r++) {
			printf("%c ", int_to_char(r));
			for (int s = 0; s < 3; s++) {
				printf("%d ", tot_pairs[r][s][i]);
			}
			printf("\n");
		}
		printf("\n\n");
	} */
}

int get_distance(int x, int y) {
	x++; y++;
	for (int k = 0; k < 3; k++) {
		int count_a = occur[0][k][y] - occur[0][k][x - 1];
		int count_b = occur[1][k][y] - occur[1][k][x - 1];
		if (count_a != count_b) {
			return -1;
		}
	}

	int num_diff = diff[y] - diff[x - 1];
	int num_pairs = 0;
	for (int r = 0; r < 3; r++) {
		for (int s = r + 1; s < 3; s++) {
			int r_to_s = tot_pairs[r][s][y] - tot_pairs[r][s][x - 1];
			int s_to_r = tot_pairs[s][r][y] - tot_pairs[s][r][x - 1];
			num_pairs += min(r_to_s, s_to_r);
		}
	}
	int num_triples = (num_diff - 2 * num_pairs) / 3;
	// printf("%d %d %d\n", num_diff, num_pairs, num_triples);
	return num_pairs + 2 * num_triples;
}

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