Submission #842460

#	Time	Username	Problem	Language	Result	Execution time	Memory
842460		ach00	Mutating DNA (IOI21_dna)	C++17	56 / 100	36 ms	6684 KiB

dna

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

vector<array<int,3>> p_a, p_b;
vector<int> diff;
int n;
// A,T,C
void init(string a, string b) {
	n = a.size();
	p_a.resize(n+1, {0,0,0});
	p_b.resize(n+1,{0,0,0});
	diff.resize(n+1,0);
	for(int i = 0; i < n; i++) {
		if(a[i]=='A') {
			p_a[i+1] = {p_a[i][0] + 1, p_a[i][1], p_a[i][2]};
		} else if(a[i] == 'T') {
			p_a[i+1] = {p_a[i][0], p_a[i][1]+1, p_a[i][2]};
		} else {
			p_a[i+1] = {p_a[i][0], p_a[i][1], p_a[i][2]+1};
		}
		if(b[i]=='A') {
			p_b[i+1] = {p_b[i][0] + 1, p_b[i][1], p_b[i][2]};
		} else if(b[i] == 'T') {
			p_b[i+1] = {p_b[i][0], p_b[i][1]+1, p_b[i][2]};
		} else {
			p_b[i+1] = {p_b[i][0], p_b[i][1], p_b[i][2]+1};
		}
		diff[i+1] = diff[i] + (!(a[i]==b[i]));
	}
}

int get_distance(int x, int y) {
	auto prx_a = p_a[x];
	auto prx_b = p_b[x];
	auto pry_a = p_a[y+1];
	auto pry_b = p_b[y+1];
	int d = diff[y+1] - diff[x];
	if(pry_a[0] - prx_a[0] != pry_b[0] - prx_b[0]) {
		return -1;
	}
	if(pry_a[1] - prx_a[1] != pry_b[1] - prx_b[1]) {
		return -1;
	}
	if(pry_a[2] - prx_a[2] != pry_b[2] - prx_b[2]) {
		return -1;
	}
	return d/2 + (d&1);
}

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