Submission #446775

#	Time	Username	Problem	Language	Result	Execution time	Memory
446775		binsjl	Mutating DNA (IOI21_dna)	C++17	0 / 100	40 ms	4084 KiB

dna

#include "dna.h"
#include <string>
#include <cstdlib>

using namespace std;

int A[2][100005], C[2][100005], AC[100005];

void init(string a, string b) {
	int n = a.length();
	for (int i = 0; i < n; i++) {
		A[0][i + 1] = A[0][i];
		A[1][i + 1] = A[1][i];
		C[0][i + 1] = C[0][i];
		C[1][i + 1] = C[1][i];
		AC[i + 1] = AC[i];
		if (a[i] == 'A')
			A[0][i + 1]++;
		if (b[i] == 'A')
			A[1][i + 1]++;
		if (a[i] == 'C')
			C[0][i + 1]++;
		if (b[i] == 'C')
			C[1][i + 1]++;
		if (a[i] == 'A' && b[i] == 'C')
			AC[i + 1]++;
		if (a[i] == 'C' && b[i] == 'A')
			AC[i + 1]--;
	}
}

int get_distance(int x, int y) {
	if ((A[0][y + 1] - A[0][x] != A[1][y + 1] - A[1][x]) || (C[0][y + 1] - C[0][x] != C[1][y + 1] - C[1][x]))
		return -1;
	return ((y - x + 1) + abs(AC[y + 1] - AC[x])) / 2;
}

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