Submission #979200

#	Time	Username	Problem	Language	Result	Execution time	Memory
979200		KK_1729	Mutating DNA (IOI21_dna)	C++17	56 / 100	31 ms	6356 KiB

dna

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define all(a) a.begin(), a.end()
#define pb push_back
int N = 0;
vector<int> a_prefix, c_prefix, t_prefix;
vector<int> a_prefix1, c_prefix1, t_prefix1;
vector<int> same;
void init(std::string a, std::string b) {
	N = a.size();

	a_prefix.resize(N);c_prefix.resize(N);t_prefix.resize(N);
	a_prefix1.resize(N);c_prefix1.resize(N);t_prefix1.resize(N);
	if (a[0] == 'A') a_prefix[0] = 1;
	if (a[0] == 'C') c_prefix[0] = 1;
	if (a[0] == 'T') t_prefix[0] = 1;

	if (b[0] == 'A') a_prefix1[0] = 1;
	if (b[0] == 'C') c_prefix1[0] = 1;
	if (b[0] == 'T') t_prefix1[0] = 1;
	FOR(i,1,N){
		a_prefix[i] = a_prefix[i-1];c_prefix[i] = c_prefix[i-1];t_prefix[i] = t_prefix[i-1];
		if (a[i] == 'A') a_prefix[i]++;
		if (a[i] == 'C') c_prefix[i]++;
		if (a[i] == 'T') t_prefix[i]++;


		a_prefix1[i] = a_prefix1[i-1];c_prefix1[i] = c_prefix1[i-1];t_prefix1[i] = t_prefix1[i-1];
		if (b[i] == 'A') a_prefix1[i]++;
		if (b[i] == 'C') c_prefix1[i]++;
		if (b[i] == 'T') t_prefix1[i]++;
	}
	same.resize(N);
	if (a[0] != b[0]) same[0] = 1;
	FOR(i,1,N){
		same[i] = same[i-1];
		if (a[i] != b[i]) same[i]++;
	}
}

int get_distance(int x, int y) {
	int a_count = a_prefix[y], c_count = c_prefix[y], t_count = t_prefix[y];
	int a_count1 = a_prefix1[y], c_count1 = c_prefix1[y], t_count1 = t_prefix1[y];
	if (x){
		a_count -= a_prefix[x-1];c_count -= c_prefix[x-1];t_count -= t_prefix[x-1];
		a_count1 -= a_prefix1[x-1]; c_count1 -= c_prefix1[x-1]; t_count1 -= t_prefix1[x-1];
	}
	if (a_count-a_count1 == 0 && c_count-c_count1 == 0 && t_count-t_count1 == 0){
		int o = same[y];
		if (x) o -= same[x-1];
		return (o+1)/2;
	}
	return -1;
}

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