Submission #625318

#	Time	Username	Problem	Language	Result	Execution time	Memory
625318		jole	Mutating DNA (IOI21_dna)	C++17	0 / 100	29 ms	4236 KiB

dna

#include <iostream>
#include <vector>

using namespace std;

struct Entry {
	int at, ac, tc;
};

vector<Entry> A;

void
init(string X, string Y) {
	int N = X.size();

	A.clear();
	A.reserve(N);

	for(int i = 0; i < N; ++i) {
		char x = X[i];
		char y = Y[i];

		int at = (x == 'A' && y == 'T') - (x == 'T' && y == 'A');
		int ac = (x == 'A' && y == 'C') - (x == 'C' && y == 'A');
		int tc = (x == 'T' && y == 'C') - (x == 'C' && y == 'T');

		if(i > 0) {
			Entry e = A[i-1];
			at += e.at;
			ac += e.ac;
			tc += e.tc;
		}
		A[i] = Entry {
			at, ac, tc
		};
	}
}

int
get_distance(int x, int y) {
	Entry a = A[x];
	Entry b = A[y];

	int at = b.at - a.at;
	int ac = b.ac - a.ac;
	int tc = b.tc - a.tc;

	// AT -> AT
	// TC -> CT

	// we can swap AT with TC to get AC

	int remaining = abs(at) + abs(ac) + abs(tc);
	int swaps = (y - x + 1) - remaining;

	if(at == tc) {
		int swapped = abs(at);
		ac += at;

		at = 0;
		tc = 0;
		// changes 
		if(ac != 0) {
			return -1;
		}

		swaps += swapped;
	}

	return swaps;
}

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