Submission #437655

#	Time	Username	Problem	Language	Result	Execution time	Memory
437655		PinkRabbit	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	6256 KiB

dna

// PinkRabbit

#include "dna.h"
#include <algorithm>
#include <string>
#include <map>

const int MN = 100005;

int N;
char a[MN], b[MN];
int sum[MN][3][3];

void init(std::string t_a, std::string t_b) {
	N = (int)t_a.length();
	for (int i = 1; i <= N; ++i)
		a[i] = t_a[i - 1],
		b[i] = t_b[i - 1];
	
	std::map<char, int> mp;
	mp['A'] = 0;
	mp['T'] = 1;
	mp['C'] = 2;
	
	for (int i = 1; i <= N; ++i) {
		for (int j1 = 0; j1 < 3; ++j1)
			for (int j2 = 0; j2 < 3; ++j2)
				sum[i][j1][j2] = sum[i - 1][j1][j2];
		int c1 = mp[a[i]];
		int c2 = mp[b[i]];
		++sum[i][c1][c2];
	}
}

int get_distance(int x, int y) {
	++x, ++y;
	int ans = y - x + 1;
	static int buk[3][3];
	for (int j1 = 0; j1 < 3; ++j1)
		for (int j2 = 0; j2 < 3; ++j2)
			buk[j1][j2] = sum[y][j1][j2] - sum[x - 1][j1][j2];
	for (int j = 0; j < 3; ++j)
		ans -= buk[j][j], buk[j][j] = 0;
	for (int j = 0; j < 3; ++j) {
		int k = (j + 1) % 3;
		int c = std::min(buk[j][k], buk[k][j]);
		ans -= c;
		buk[j][k] -= c;
		buk[k][j] -= c;
	}
	if (buk[0][1]) {
		int c = std::min({buk[0][1], buk[1][2], buk[2][0]});
		ans -= c;
		buk[0][1] -= c;
		buk[1][2] -= c;
		buk[2][0] -= c;
	} else {
		int c = std::min({buk[0][2], buk[2][1], buk[1][0]});
		ans -= c;
		buk[0][2] -= c;
		buk[2][1] -= c;
		buk[1][0] -= c;
	}
	for (int j1 = 0; j1 < 3; ++j1)
		for (int j2 = 0; j2 < 3; ++j2)
			if (buk[j1][j2])
				return -1;
	return ans;
}

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