Submission #1265257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265257		canhnam357	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	24 ms	7176 KiB

dna

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

const int N = 1e5 + 1;
int p[3][N] = {}, pre[3][3][N] = {};
void init(std::string a, std::string b) {
	int n = a.size();
	string t = "ATC";
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++) p[j][i + 1] += p[j][i];
		int f = t.find(a[i]);
		p[f][i + 1]++;
		int s = t.find(b[i]);
		p[s][i + 1]--;
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				pre[j][k][i + 1] += pre[j][k][i];
			}
		}
		if (f != s) pre[f][s][i + 1]++;
	}
}

int get_distance(int x, int y) {
	for (int i = 0; i < 3; i++)
	{
		if (p[i][y + 1] != p[i][x]) return -1;
	}
	int a[3][3] = {};
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			a[i][j] = pre[i][j][y + 1] - pre[i][j][x];
		}
	}
	int ans = 0, rem = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = i + 1; j < 3; j++)
		{
			int k = min(a[i][j], a[j][i]);
			ans += k;
			a[i][j] -= k;
			a[j][i] -= k;
		}
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++) rem += a[i][j];
	}
	assert(rem % 3 == 0);
	return ans + rem / 3 * 2;
}

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