제출 #476803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476803		Drew_	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	50 ms	9716 KiB

dna

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

constexpr int MAX = 1e5 + 69;

int n;
int fqa[MAX][3] = {}, fqb[MAX][3] = {};
int tf[MAX][3][3] = {};

void init(string a, string b) {
	n = (int) a.size();

	const auto get = [](char c) -> int
	{
		if (c == 'A')
			return 0;
		if (c == 'T')
			return 1;
		return 2;
	};	

	for (int i = 1; i <= n; ++i)
	{
		int x = get(a[i-1]), y = get(b[i-1]);
		fqa[i][x] = 1; fqb[i][y] = 1;
		tf[i][x][y] = 1;
	}

	for (int j = 0; j < 3; ++j)
		for (int i = 1; i <= n; ++i)
			fqa[i][j] += fqa[i-1][j], fqb[i][j] += fqb[i-1][j];

	for (int j = 0; j < 3; ++j)
		for (int k = 0; k < 3; ++k)
			for (int i = 1; i <= n; ++i)
				tf[i][j][k] +=  tf[i-1][j][k];
}

int get_distance(int l, int r) {
	l++, r++;

	for (int i = 0; i < 3; ++i)
		if (fqa[r][i] - fqa[l-1][i] != fqb[r][i] - fqb[l-1][i])
			return -1;

	int res = r-l+1, ctr = 0;
	for (int i = 0; i < 3; ++i)
		res -= (tf[r][i][i] - tf[l-1][i][i]);

	for (int i = 0; i < 3; ++i)
		for (int j = i+1; j < 3; ++j)
		{
			ctr += min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
			res -= 2 * min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
		}

	assert(res % 3 == 0);
	return ctr + 2*res/3;
}

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