Submission #819373

#	Time	Username	Problem	Language	Result	Execution time	Memory
819373		gesgha	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	9756 KiB

dna

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

#define fi first
#define se second
#define pb push_back

#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()

using namespace std;


template <typename T>
bool umx(T &x, T& y) {
	return x < y ? x = y, 1 : 0;
}

template <typename T>
bool umn(T &x, T& y) {
	return x > y ? x = y, 1 : 0;
}

using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;


const int N = 3e5 + 100;



int n;
int ca[N][3];
int cb[N][3];

int CNT[N][3][3];
int VAL[N];
void init(string a, string b) {
	VAL['A'] = 0;
	VAL['T'] = 1;
	VAL['C'] = 2;
	int n = sz(a);
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A') ca[i][0] = 1;
		else if (a[i] == 'T') ca[i][1] = 1;
		else if (a[i] == 'C') ca[i][2] = 1;
		if (i) {
			for (int j = 0; j < 3; j++) ca[i][j] += ca[i - 1][j];
		}
	}
	for (int i = 0; i < n; i++) {
		if (b[i] == 'A') cb[i][0] = 1;
		else if (b[i] == 'T') cb[i][1] = 1;
		else if (b[i] == 'C') cb[i][2] = 1;
		if (i) {
			for (int j = 0; j < 3; j++) cb[i][j] += cb[i - 1][j];
		}
	}
	for (int i = 0; i < n; i++) {
		int x = VAL[a[i]], y = VAL[b[i]];
		CNT[i][x][y] = 1;
		if (i) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) CNT[i][j][k] += CNT[i - 1][j][k];
			}
		}
	}
}

int get_distance(int x, int y) {
	for (int i = 0; i < 3; i++) {
		int c1 = ca[y][i], c2 = cb[y][i];
		if (x) {
			c1 -= ca[x - 1][i];
			c2 -= cb[x - 1][i];
		}
		if (c1 != c2) return -1;
	}
	int C[3][3] = {};
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			C[i][j] = CNT[y][i][j];
			if (x) C[i][j] -= CNT[x - 1][i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			int X = min(C[i][j], C[j][i]);
			ans += X;
			C[i][j] -= X;
			C[j][i] -= X;
		}
	}
	int ws = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if(i == j) continue;
			ans += C[i][j];
			umx(ws, C[i][j]);
		}
	}
	ans -= ws;
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:62:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |   int x = VAL[a[i]], y = VAL[b[i]];
      |                   ^
dna.cpp:62:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |   int x = VAL[a[i]], y = VAL[b[i]];
      |                                  ^

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