Submission #793775

#	Time	Username	Problem	Language	Result	Execution time	Memory
793775		Johann	Mutating DNA (IOI21_dna)	C++17	100 / 100	105 ms	13888 KiB

dna

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

typedef vector<int> vi;
#define sz(x) (int)(x).size()

vector<int> str[2];
int N;

struct node
{
	int data[3][3];
	node()
	{
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				data[i][j] = 0;
	}
};
node operator+(const node &a, const node &b)
{
	node ret;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			ret.data[i][j] = a.data[i][j] + b.data[i][j];
	return ret;
}
const node EMPTY;

struct segtree
{
	int size;
	vector<node> arr;
	void init()
	{
		size = 1;
		while (size < N)
			size *= 2;
		arr.resize(2 * size);
		for (int i = 0; i < N; ++i)
			++arr[size + i].data[str[0][i]][str[1][i]];
		for (int i = size - 1; i > 0; --i)
			arr[i] = arr[2 * i] + arr[2 * i + 1];
	}
	node query(int l, int r)
	{
		return query(l, r, 1, 0, size);
	}
	node query(int l, int r, int x, int lx, int rx)
	{
		if (l <= lx && rx <= r)
			return arr[x];
		if (r <= lx || rx <= l)
			return EMPTY;

		int m = (lx + rx) / 2;
		return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx);
	}
};
segtree seg;

void init(std::string a, std::string b)
{
	N = sz(a);
	str[0].resize(N), str[1].resize(N);
	vi trans(128, -1);
	trans['A'] = 0;
	trans['C'] = 1;
	trans['T'] = 2;
	for (int i = 0; i < N; ++i)
		str[0][i] = trans[a[i]], str[1][i] = trans[b[i]];
	seg.init();
}

int get_distance(int x, int y)
{
	node tmp = seg.query(x, y + 1);
	int moves = 0;
	for (int i = 0; i < 3; ++i)
		tmp.data[i][i] = 0;

	int cnt[3] = {0, 0, 0};
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			cnt[i] += tmp.data[i][j], cnt[j] -= tmp.data[i][j];
	for (int i = 0; i < 3; ++i)
		if (cnt[i] != 0)
			return -1;

	int v = 0;
	for (int i = 0; i < 3; ++i)
		for (int j = i + 1; j < 3; ++j)
		{
			int mini = min(tmp.data[i][j], tmp.data[j][i]);
			moves += mini;
			tmp.data[i][j] -= mini;
			tmp.data[j][i] -= mini;
			v = max(v, max(tmp.data[i][j], tmp.data[j][i]));
		}

	moves += 2 * v;
	return moves;
}

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