Submission #818104

#	Time	Username	Problem	Language	Result	Execution time	Memory
818104		LittleCube	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	7816 KiB

dna

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

int n, S[100005][3], P[100005][7], s[3], p[6];

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

int pch(char c, char d)
{
	if (c == 'A' && d == 'T')
		return 0;
	if (c == 'T' && d == 'A')
		return 1;
	if (c == 'A' && d == 'C')
		return 2;
	if (c == 'C' && d == 'A')
		return 3;
	if (c == 'C' && d == 'T')
		return 4;
	if (c == 'T' && d == 'C')
		return 5;
	return 6;
}

void init(std::string a, std::string b)
{
	n = a.size();
	a = ' ' + a;
	b = ' ' + b;
	for (int i = 1; i <= n; i++)
		S[i][ch(a[i])]++, S[i][ch(b[i])]--, P[i][pch(a[i], b[i])]++;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
			S[i][j] += S[i - 1][j];
		for (int j = 0; j < 6; j++)
			P[i][j] += P[i - 1][j];
	}
}

int get_distance(int x, int y)
{
	y++;
	for (int j = 0; j < 3; j++)
	{
		s[j] = S[y][j] - S[x][j];
		if (s[j])
			return -1;
	}
	for (int j = 0; j < 6; j++)
		p[j] = P[y][j] - P[x][j];
	int ans = 0;
	for (int j = 0; j < 6; j += 2)
	{
		int m = min(p[j], p[j ^ 1]);
		ans += m;
		p[j] -= m;
		p[j ^ 1] -= m;
	}
	return ans + max(p[0], p[1]) * 2;
}

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