Submission #437372

#	Time	Username	Problem	Language	Result	Execution time	Memory
437372		Mohammed_Atalah	Mutating DNA (IOI21_dna)	C++17	100 / 100	131 ms	12800 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;


vector<int64_t> T1;
vector<int64_t> T2;
vector<int64_t> A1;
vector<int64_t> A2;
vector<int64_t> C1;
vector<int64_t> C2;


vector<int64_t> AC;
vector<int64_t> CA;
vector<int64_t> AT;
vector<int64_t> TA;
vector<int64_t> CT;
vector<int64_t> TC;

vector<int64_t> same;

void init(std::string a, std::string b) {

	int64_t len = a.size();

	T1.resize(len + 1);
	T2.resize(len + 1);
	A1.resize(len + 1);
	A2.resize(len + 1);
	C1.resize(len + 1);
	C2.resize(len + 1);


	TA.resize(len + 1);
	TC.resize(len + 1);
	AC.resize(len + 1);
	AT.resize(len + 1);
	CT.resize(len + 1);
	CA.resize(len + 1);


	same.resize(len + 1);



	int64_t currA1 = 0;
	int64_t currT1 = 0;
	int64_t currA2 = 0;
	int64_t currT2 = 0;
	int64_t currC1 = 0;
	int64_t currC2 = 0;
	int64_t currsame = 0;

	int64_t currAT = 0;
	int64_t currTA = 0;
	int64_t currAC = 0;
	int64_t currTC = 0;
	int64_t currCA = 0;
	int64_t currCT = 0;



	for (int i = 0; i < len; i++) {
		if (a[i] == 'A') {
			currA1++;
		} else if (a[i] == 'T') {
			currT1++;
		} else if (a[i] == 'C') {
			currC1++;
		}


		if (b[i] == 'A') {
			currA2++;
		} else if (b[i] == 'T') {
			currT2++;
		} else if (b[i] == 'C') {
			currC2++;
		}

		if (a[i] == b[i]) {
			currsame++;
		}


		if (a[i] == 'A' && b[i] == 'T') {
			currAT++;
		} else if (a[i] == 'A' && b[i] == 'C') {
			currAC++;
		} else if (a[i] == 'C' && b[i] == 'A') {
			currCA++;
		} else if (a[i] == 'C' && b[i] == 'T') {
			currCT++;
		} else if (a[i] == 'T' && b[i] == 'A') {
			currTA++;
		} else if (a[i] == 'T' && b[i] == 'C') {
			currTC++;
		}

		A1[i + 1] = currA1;
		T1[i + 1] = currT1;
		A2[i + 1] = currA2;
		T2[i + 1] = currT2;
		C1[i + 1] = currC1;
		C2[i + 1] = currC2;

		AC[i + 1] = currAC;
		TA[i + 1] = currTA;
		AT[i + 1] = currAT;
		TC[i + 1] = currTC;
		CT[i + 1] = currCT;
		CA[i + 1] = currCA;


		same[i + 1] = currsame;


	}



}

int get_distance(int x, int y) {

	int64_t a1 = A1[y + 1] - A1[x];
	int64_t t1 = T1[y + 1] - T1[x];
	int64_t c1 = C1[y + 1] - C1[x];
	int64_t a2 = A2[y + 1] - A2[x];
	int64_t t2 = T2[y + 1] - T2[x];
	int64_t c2 = C2[y + 1] - C2[x];


	int64_t at = AT[y + 1] - AT[x];
	int64_t ac = AC[y + 1] - AC[x];
	int64_t ta = TA[y + 1] - TA[x];
	int64_t tc = TC[y + 1] - TC[x];
	int64_t ca = CA[y + 1] - CA[x];
	int64_t ct = CT[y + 1] - CT[x];

	int64_t s = same[y + 1] - same[x];
	// cout << s << endl;

	if (t1 != t2 || a1 != a2 || c1 != c2) {
		return -1;
	}
	int res = 0;
	res += min(ac, ca);
	res += min(at, ta);
	res += min(tc, ct);
	res += abs(ac - ca) * 2;
	return res;

}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:143:10: warning: unused variable 's' [-Wunused-variable]
  143 |  int64_t s = same[y + 1] - same[x];
      |          ^

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