Submission #552815

#	Time	Username	Problem	Language	Result	Execution time	Memory
552815		Jomnoi	Mutating DNA (IOI21_dna)	C++17	35 / 100	36 ms	7048 KiB

dna

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

const int MAX_N = 1e5 + 10;

int N;
int preT1[MAX_N], preA1[MAX_N], preC1[MAX_N];
int preT2[MAX_N], preA2[MAX_N], preC2[MAX_N];
int preTA[MAX_N], preAT[MAX_N];

void init(string a, string b) {
	N = a.length();
	for(int i = 1; i <= N; i++) {
		preT1[i] = preT1[i - 1] + (a[i - 1] == 'T');
		preT2[i] = preT2[i - 1] + (b[i - 1] == 'T');
		preA1[i] = preA1[i - 1] + (a[i - 1] == 'A');
		preA2[i] = preA2[i - 1] + (b[i - 1] == 'A');
		preC1[i] = preC1[i - 1] + (a[i - 1] == 'C');
		preC2[i] = preC2[i - 1] + (b[i - 1] == 'C');
		preTA[i] = preTA[i - 1] + (a[i - 1] == 'T' and b[i - 1] == 'A');
		preAT[i] = preAT[i - 1] + (a[i - 1] == 'A' and b[i - 1] == 'T');
	}
}

int range(int x, int y, int *a) {
	return a[y + 1] - a[x];
}

int get_distance(int x, int y) {
	if(range(x, y, preT1) != range(x, y, preT2) or range(x, y, preA1) != range(x, y, preA2) or range(x, y, preC1) != range(x, y, preC2)) {
		return -1;
	}

	return min(range(x, y, preTA), range(x, y, preAT));
}

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