Submission #1048297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048297		AmirAli_H1	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	13080 KiB

dna

// In the name of Allah

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

typedef		long long				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

const int maxn = 2e5 + 7;

int n;
int A1[maxn], A2[maxn];
pair<int, pii> sm1[maxn], sm2[maxn];
int smx[3][3][maxn]; int val[3][3];

bool ok(int l, int r) {
	if (sm1[r].F - sm1[l].F != sm2[r].F - sm2[l].F) return 0;
	if (sm1[r].S.F - sm1[l].S.F != sm2[r].S.F - sm2[l].S.F) return 0;
	if (sm1[r].S.S - sm1[l].S.S != sm2[r].S.S - sm2[l].S.S) return 0;
	return 1;
}

void init(string a, string b) {
	n = len(a);
	for (int i = 1; i <= n; i++) {
		if (a[i - 1] == 'A') A1[i] = 0;
		else if (a[i - 1] == 'T') A1[i] = 1;
		else if (a[i - 1] == 'C') A1[i] = 2;
		if (b[i - 1] == 'A') A2[i] = 0;
		else if (b[i - 1] == 'T') A2[i] = 1;
		else if (b[i - 1] == 'C') A2[i] = 2;
	}
	
	for (int i = 1; i <= n; i++) {
		sm1[i].F = sm1[i - 1].F + (A1[i] == 0);
		sm1[i].S.F = sm1[i - 1].S.F + (A1[i] == 1);
		sm1[i].S.S = sm1[i - 1].S.S + (A1[i] == 2);
		sm2[i].F = sm2[i - 1].F + (A2[i] == 0);
		sm2[i].S.F = sm2[i - 1].S.F + (A2[i] == 1);
		sm2[i].S.S = sm2[i - 1].S.S + (A2[i] == 2);
	}
	
	for (int R1 = 0; R1 < 3; R1++) {
		for (int R2 = 0; R2 < 3; R2++) {
			for (int i = 1; i <= n; i++) {
				smx[R1][R2][i] = smx[R1][R2][i - 1] + (A1[i] == R1 && A2[i] == R2);
			}
		}
	}
}

int get_distance(int l, int r) {
	r++;
	if (!ok(l, r)) return -1;
	
	for (int R1 = 0; R1 < 3; R1++) {
		for (int R2 = 0; R2 < 3; R2++) {
			val[R1][R2] = smx[R1][R2][r] - smx[R1][R2][l];
		}
	}
	
	ll res = 0;
	ll d1 = min(val[0][1], val[1][0]);
	val[0][1] -= d1; val[1][0] -= d1;
	res += d1;
	
	ll d2 = min(val[0][2], val[2][0]);
	val[0][2] -= d2; val[2][0] -= d2;
	res += d2;
	
	ll d3 = min(val[1][2], val[2][1]);
	val[1][2] -= d3; val[2][1] -= d3;
	res += d3;
	
	res += 2 * (val[0][1] + val[1][0]);
	return res;
}

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