제출 #1195731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195731		belgianbot	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	132 ms	22344 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<vector<int>>> pref;
map<char, int> mp;
int n;
void init(std::string a, std::string b) {
	n = a.size();
	pref.resize(a.size(), vector<vector<int>>(3, vector<int>(3,0)));
	mp['T'] = 0; mp['A'] = 1; mp['C'] = 2;

	for (int i = 0; i < a.size(); i++) {
		if (i) pref[i] = pref[i-1];
		pref[i][mp[a[i]]][mp[b[i]]]++;
	}
}

int get_distance(int x, int y) {
	int res = 0;
	vector<vector<int>> vec = {{0,0,0},{0,0,0},{0,0,0}};
	if (x) vec = pref[x-1];
	auto vec2 = pref[y];

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) vec2[i][j] -= vec[i][j];
	}
	for (int i = 0; i < 3; i++) {
		if (vec2[i][0] + vec2[i][1] + vec2[i][2] != vec2[0][i] + vec2[1][i] + vec2[2][i]) return -1;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			int mini = min(vec2[i][j], vec2[j][i]);
			res += mini;
			vec2[i][j] -= mini;
			vec2[j][i] -= mini;
		}
	}
	int left = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			left += vec2[i][j];
		}
	}
	res += left / 3 * 2;
	return res;
}

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