Submission #1064247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064247		fv3	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	10940 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

int N;
vector<vector<int>> ps;
vector<int> ps_a, ps_t, ps_c;

string A, B;

void init(std::string a, std::string b) 
{
	int N = a.size();
	A = a;
	B = b;

	// Construct prefix sums
	ps = vector<vector<int>>(N+1, vector<int>(6));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 6; j++)
			ps[i+1][j] = ps[i][j];

		if (a[i] == 'A' && b[i] == 'T')
			ps[i+1][0]++;
		if (a[i] == 'A' && b[i] == 'C')
			ps[i+1][1]++;
		if (a[i] == 'C' && b[i] == 'T')
			ps[i+1][2]++;
		if (a[i] == 'T' && b[i] == 'A')
			ps[i+1][3]++;
		if (a[i] == 'C' && b[i] == 'A')
			ps[i+1][4]++;
		if (a[i] == 'T' && b[i] == 'C')
			ps[i+1][5]++;
	}

	ps_a = ps_t = ps_c = vector<int>(N + 1);
	for (int i = 0; i < N; i++)
		ps_a[i+1] = ps_a[i] + (int)(a[i] == 'A') - (int)(b[i] == 'A');

	for (int i = 0; i < N; i++)
		ps_t[i+1] = ps_t[i] + (int)(a[i] == 'T') - (int)(b[i] == 'T');

	for (int i = 0; i < N; i++)
		ps_c[i+1] = ps_c[i] + (int)(a[i] == 'C') - (int)(b[i] == 'C');
}

int get_distance(int x, int y) 
{
	if (ps_a[y+1] - ps_a[x] != 0 || ps_t[y+1] - ps_t[x] != 0 || ps_c[y+1] - ps_c[x] != 0)
	{
		return -1;
	}
	vector<int> v(6);
	for (int i = 0; i < 6; i++)
		v[i] = ps[y+1][i] - ps[x][i];

	int res = 0;
	for (int i = 0; i < 3; i++)
	{
		int n = min(v[i], v[i+3]);
		res += n;

		v[i] -= n;
		v[i+3] -= n;
	}
	
	if (v[0] + v[3] != v[1] + v[4] || v[0] + v[3] != v[2] + v[5])
		return -1;

	return res + (v[0] + v[3]) * 2;
}

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