Submission #1009415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009415		aParrot	Mutating DNA (IOI21_dna)	C++17	21 / 100	30 ms	7180 KiB

dna

#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
const int N = 100000;
// const int N = 6;

// cnt_string_letter
vector<int> cnt_a_a(N+1), cnt_a_t(N+1), cnt_a_c(N+1);
vector<int> cnt_b_a(N+1), cnt_b_t(N+1), cnt_b_c(N+1);
vector<int> ov_a(N+1), ov_t(N+1), ov_c(N+1);

void init(string a, string b) {
	cnt_a_a[0]=0;
	cnt_a_t[0]=0;
	cnt_a_c[0]=0;
	cnt_b_a[0]=0;
	cnt_b_t[0]=0;
	cnt_b_c[0]=0;
	ov_a[0]=0;
	ov_t[0]=0;
	ov_c[0]=0;
	
	for (int i=1; i<=(int)a.length(); i++) {
		// count prefix sums
		cnt_a_a[i] = cnt_a_a[i-1] + (a[i-1]=='A');
		cnt_b_a[i] = cnt_b_a[i-1] + (b[i-1]=='A');
		cnt_a_t[i] = cnt_a_t[i-1] + (a[i-1]=='T');
		cnt_b_t[i] = cnt_b_t[i-1] + (b[i-1]=='T');
		cnt_a_c[i] = cnt_a_c[i-1] + (a[i-1]=='C');
		cnt_b_c[i] = cnt_b_c[i-1] + (b[i-1]=='C');

		// overlap prefix sums
		ov_a[i] = ov_a[i-1] + (a[i-1]=='A' && (a[i-1] != b[i-1]));
		ov_t[i] = ov_t[i-1] + (a[i-1]=='T' && (a[i-1] != b[i-1]));
		ov_c[i] = ov_c[i-1] + (a[i-1]=='C' && (a[i-1] != b[i-1]));
	}


	// cout << "init:" << endl;
	// print_bitset(bita);
	// print_bitset(bitb);
	// cout << endl;
}

int get_distance(int x, int y) {
	// cerr << endl;
	// cerr << "get_distance(" << x << ", " << y << ")" << endl;	
	// check if counts align
	int a_a_cnt = (cnt_a_a[y+1] - cnt_a_a[x]);
	int b_a_cnt = (cnt_b_a[y+1] - cnt_b_a[x]);
	int a_t_cnt = (cnt_a_t[y+1] - cnt_a_t[x]);
	int b_t_cnt = (cnt_b_t[y+1] - cnt_b_t[x]);
	int a_c_cnt = (cnt_a_c[y+1] - cnt_a_c[x]);
	int b_c_cnt = (cnt_b_c[y+1] - cnt_b_c[x]);
	bool a_cnt_match = a_a_cnt == b_a_cnt;
	bool t_cnt_match = a_t_cnt == b_t_cnt;
	bool c_cnt_match = a_c_cnt == b_c_cnt;
	// cerr << "A count" << endl;
	// cerr << a_a_cnt << " " << b_a_cnt << endl;
	// cerr << "T count" << endl;
	// cerr << a_t_cnt << " " << b_t_cnt << endl;
	// cerr << "C count" << endl;
	// cerr << a_c_cnt << " " << b_c_cnt << endl;
	if (!a_cnt_match || !t_cnt_match || !c_cnt_match) {
		return -1;
	}

	// calculate the distance
	int ov_cnt_a = ov_a[y+1] - ov_a[x];
	int ov_cnt_t = ov_t[y+1] - ov_t[x];
	int ov_cnt_c = ov_c[y+1] - ov_c[x];
	
	// one of the characters don't need to be changed
	if (ov_cnt_a == 0 || ov_cnt_t == 0 || ov_cnt_c == 0) {
		// cerr << "one of characters" << endl;
		int sm = ov_cnt_a + ov_cnt_t + ov_cnt_c;
		return (sm+(sm-1))/2;
	}

	// cerr << "algorithm" << endl;
	vector<int> sums = {ov_cnt_a, ov_cnt_t, ov_cnt_c};
	sort(sums.begin(), sums.end());
	return sums[0] + sums[1];
}

// int main() {
// 	// init("AAABBB", "BBBAAA");
// 	init("ATACAT", "ACTATA");
// 	cerr << get_distance(1, 3) << endl;
// 	cerr << get_distance(4, 5) << endl;
// 	cerr << get_distance(3, 5) << endl;

// 	return 0;
// }

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