Submission #437088

#	Time	Username	Problem	Language	Result	Execution time	Memory
437088		aryan12	Mutating DNA (IOI21_dna)	C++17	100 / 100	61 ms	9212 KiB

dna

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

const int N = 1e5 + 5; 
int prefA[N][3], prefB[N][3];
int pref[N][3][3];

void init(string a, string b) {
	int n = a.size();
	int arrA[n + 1], arrB[n + 1];
	for(int i = 0; i < a.size(); i++) {
		arrA[i + 1] = ((a[i] == 'A') ? 0 : ((a[i] == 'C') ? 1 : 2));
		arrB[i + 1] = ((b[i] == 'A') ? 0 : ((b[i] == 'C') ? 1 : 2));
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 3; j++) {
			prefA[i][j] = 0;
			prefB[i][j] = 0;
			for(int k = 0; k < 3; k++) {
				pref[i][j][k] = 0;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			prefA[i][j] = prefA[i - 1][j];
			prefB[i][j] = prefB[i - 1][j];
			for(int k = 0; k < 3; k++) {
				pref[i][j][k] = pref[i - 1][j][k];
			}
		}
		prefA[i][arrA[i]]++;
		prefB[i][arrB[i]]++;
		pref[i][arrA[i]][arrB[i]]++;
	}
}

int get_distance(int x, int y) {
	x++, y++;
	if((prefA[y][0] - prefA[x - 1][0] != prefB[y][0] - prefB[x - 1][0]) || (prefA[y][1] - prefA[x - 1][1] != prefB[y][1] - prefB[x - 1][1]) || (prefA[y][2] - prefA[x - 1][2] != prefB[y][2] - prefB[x - 1][2])) {
		return -1;
	}
	int res = 0;
	int ans[3] = {0, 0, 0};
	int carry[3] = {0, 0, 0};
	ans[0] += min(pref[y][0][1] - pref[x - 1][0][1], pref[y][1][0] - pref[x - 1][1][0]);
	ans[1] += min(pref[y][0][2] - pref[x - 1][0][2], pref[y][2][0] - pref[x - 1][2][0]);
	ans[2] += min(pref[y][1][2] - pref[x - 1][1][2], pref[y][2][1] - pref[x - 1][2][1]);
	//cout << "ans[0] = " << ans[0] << ", ans[1] = " << ans[1] << ", ans[2] = " << ans[2] << "\n";
	int sum = ans[0] + ans[1] + ans[2];
	res = sum;
	int left = y - x + 1 - sum * 2;
	left -= (pref[y][0][0] - pref[x - 1][0][0] + pref[y][1][1] - pref[x - 1][1][1] + pref[y][2][2] - pref[x - 1][2][2]);
	//cout << "left = " << left << ", x = " << x << ", y = " << y << "\n";
	assert(left % 3 == 0);
	res += (left / 3) * 2;
	return res;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:46:6: warning: unused variable 'carry' [-Wunused-variable]
   46 |  int carry[3] = {0, 0, 0};
      |      ^~~~~

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