Submission #620810

#	Time	Username	Problem	Language	Result	Execution time	Memory
620810		HamletPetrosyan	Mutating DNA (IOI21_dna)	C++17	100 / 100	65 ms	17560 KiB

dna

#include "dna.h"
using namespace std;

#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()

const int N = 1e5 + 5;

int cnt[2][N][5];
int c[N][5][5];

void init(string a, string b) {
	for(int i = 0; i < len(a); i++){
		cnt[0][i + 1][0] = cnt[0][i][0] + (a[i] == 'A');
		cnt[0][i + 1][1] = cnt[0][i][1] + (a[i] == 'C');
		cnt[0][i + 1][2] = cnt[0][i][2] + (a[i] == 'T');

		c[i + 1][0][1] = c[i][0][1] + (a[i] == 'A' && b[i] == 'C');
		c[i + 1][0][2] = c[i][0][2] + (a[i] == 'A' && b[i] == 'T');
		c[i + 1][1][0] = c[i][1][0] + (a[i] == 'C' && b[i] == 'A');
		c[i + 1][1][2] = c[i][1][2] + (a[i] == 'C' && b[i] == 'T');
		c[i + 1][2][0] = c[i][2][0] + (a[i] == 'T' && b[i] == 'A');
		c[i + 1][2][1] = c[i][2][1] + (a[i] == 'T' && b[i] == 'C');
	}
	for(int i = 0; i < len(b); i++){
		cnt[1][i + 1][0] = cnt[1][i][0] + (b[i] == 'A');
		cnt[1][i + 1][1] = cnt[1][i][1] + (b[i] == 'C');
		cnt[1][i + 1][2] = cnt[1][i][2] + (b[i] == 'T');
	}
}

int get_distance(int x, int y) {
	if(cnt[0][y + 1][0] - cnt[0][x][0] != cnt[1][y + 1][0] - cnt[1][x][0]) return -1;
	if(cnt[0][y + 1][1] - cnt[0][x][1] != cnt[1][y + 1][1] - cnt[1][x][1]) return -1;
	if(cnt[0][y + 1][2] - cnt[0][x][2] != cnt[1][y + 1][2] - cnt[1][x][2]) return -1;

	int sum = 0, ret = 0, now;
	sum += c[y + 1][0][1] + c[y + 1][0][2] + c[y + 1][1][0] + c[y + 1][1][2] + c[y + 1][2][0] + c[y + 1][2][1] - (c[x][0][1] + c[x][0][2] + c[x][1][0] + c[x][1][2] + c[x][2][0] + c[x][2][1]);

	now = min(c[y + 1][0][1] - c[x][0][1], c[y + 1][1][0] - c[x][1][0]);
	ret += now;
	sum -= 2 * now;

	now = min(c[y + 1][0][2] - c[x][0][2], c[y + 1][2][0] - c[x][2][0]);
	ret += now;
	sum -= 2 * now;

	now = min(c[y + 1][2][1] - c[x][2][1], c[y + 1][1][2] - c[x][1][2]);
	ret += now;
	sum -= 2 * now;

	ret += (sum / 3) * 2;
	return ret;
}

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