Submission #566951

#	Time	Username	Problem	Language	Result	Execution time	Memory
566951		pawned	Mutating DNA (IOI21_dna)	C++17	100 / 100	58 ms	10248 KiB

dna

#include "dna.h"

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N;

int type1[100005];
int type2[100005];

int counts1[100005][3];
int counts2[100005][3];

int pfs[100005][3][3];

void init(std::string a, std::string b) {
	N = a.size();
	for (int i = 0; i < N; i++) {
		if (a[i] == 'A')
			type1[i] = 0;
		else if (a[i] == 'C')
			type1[i] = 1;
		else
			type1[i] = 2;
		if (b[i] == 'A')
			type2[i] = 0;
		else if (b[i] == 'C')
			type2[i] = 1;
		else
			type2[i] = 2;
	}
	for (int i = 0; i < 3; i++) {
		counts1[0][i] = 0;
		counts2[0][i] = 0;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			counts1[i][j] = counts1[i - 1][j];
			counts2[i][j] = counts2[i - 1][j];
		}
		counts1[i][type1[i - 1]]++;
		counts2[i][type2[i - 1]]++;
	}
/*
	cout<<"counts1: "<<endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j <= N; j++) {
			cout<<counts1[j][i]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
*/
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			pfs[0][i][j] = 0;
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				pfs[i][j][k] = pfs[i - 1][j][k];
			}
		}
		pfs[i][type1[i - 1]][type2[i - 1]]++;
	}
}

int get_distance(int x, int y) {
	int l, r;
	l = x;
  	r = y;
	bool works = true;
	for (int j = 0; j < 3; j++) {
		if ((counts1[r + 1][j] - counts1[l][j]) != (counts2[r + 1][j] - counts2[l][j]))
			works = false;
	}
	if (!works)
		return -1;
	int vals[3][3];
	for (int j = 0; j < 3; j++) {
		for (int k = 0; k < 3; k++) {
			vals[j][k] = pfs[r + 1][j][k] - pfs[l][j][k];
		}
	}
	int total = 0;
	int x1 = min(vals[0][1], vals[1][0]);
	total += x1;
	vals[0][1] -= x1;
	vals[1][0] -= x1;
	int x2 = min(vals[0][2], vals[2][0]);
	total += x2;
	vals[0][2] -= x2;
	vals[2][0] -= x2;
	int x3 = min(vals[1][2], vals[2][1]);
	total += x3;
	vals[1][2] -= x3;
	vals[2][1] -= x3;
	total += 2 * max(vals[0][1], vals[1][0]);
	return total;
}

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