Submission #1064197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064197		fv3	Mutating DNA (IOI21_dna)	C++17	35 / 100	36 ms	9552 KiB

dna

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

using namespace std;

string A, B;

int N;
vector<vector<int>> ps;

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

	// 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]++;
	}
}

int get_distance(int x, int y) 
{
	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: 0 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16