Submission #1179865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179865		madamadam3	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	32 ms	7612 KiB

dna

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

using namespace std;

#define sum(arr) (arr)[y+1] - (arr)[x]
using vi = vector<int>;
const int MAXN = 100'001;

int n;
string A, B;

int prefixA[3][MAXN];
int prefixB[3][MAXN];
int prefixDiff[6][MAXN]; // pd[0]: A, T, pd[1]: A, C, pd[2]: T, A, pd[3]: T, C, pd[4]: C, A, pd[5]: C, T

int gi(char inp) {
	if (inp == 'A') return 0;
	else if (inp == 'T') return 1;
	else return 2;
}

char g(int i) {
	if (i == 0) return 'A';
	else if (i == 1) return 'T';
	else return 'C';
}

int p(int i, int j) {
	if (i == 0 && j == 1) return 0;
	else if (i == 0 && j == 2) return 1;
	else if (i == 1 && j == 0) return 2;
	else if (i == 1 && j == 2) return 3;
	else if (i == 2 && j == 1) return 4;
	else return 5;
}
 
void init(string a, string b) {
	A = a;
	B = b;
	n = (int) a.size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			prefixA[j][i + 1] = prefixA[j][i];
			prefixB[j][i + 1] = prefixB[j][i];
		}

		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				int is_diff = (a[i] == g(j) && b[i] == g(k)) ? 1 : 0;
				prefixDiff[p(j, k)][i+1] = prefixDiff[p(j, k)][i] + is_diff; 
			}
		}

		prefixA[gi(a[i])][i+1]++;
		prefixB[gi(b[i])][i+1]++;
	}
}

int try_fix(int x, int y, int A, int T, int C) {
	/*
		What if every 'A' in a[x:y] was in the same place as in b[x:y]?
			- we could use our algorithm for subtasks where A and T are the only characters
			- this would efficiently solve the problem for any size of input, but requires this to be true
			- if every 'T' was in the right place, or every 'C', we could employ the same strategy

		What if we try to place all instances of one letter in the right place, before looking at the others?
			- some swaps will be "good": ie. swapping the elements at 2 indices i, j will result in them both
			  being taken from the incorrect position, to a correct position (eg. A on T square swaps with T on A square)
			- there may also be "bad" swaps: althought one character is in the right place, the other character does not 
			  belong on its new square (but it didnt belong on its old square either)

		assume the character we want to sort first is 'A'.
		- how many characters must we move? to_sort = total a's in subarray - number of a's on an a square
		- how many good swaps will we perform? good swaps = min(Cs on A, As on C) + min(Ts on A, As on T)
		- how many bad swaps? bad = total swaps - number of good swaps
		- how many unsorted T's and C's will there be after this process?
		- unsorted T's = original unsorted Ts - good swaps with Ts + number of bad swaps with Ts
		- unsorted C's = original unsorted Cs - good swaps with Cs + bad swaps with Cs
		- once all A's are in place, then unsorted Ts = unsorted Cs
		- and the total number of actions to fix the array = number of swaps with As + number of unsorted Ts (or Cs) after swaps
	*/

	// amounts of each character that are unsorted
	// cout << "\nUsing order {" << g(A) << ", " << g(T) << ", " << g(C) << "}\n";
	int moves = 0;

	int uA = sum(prefixDiff[p(A, T)]) + sum(prefixDiff[p(A, C)]), 
	    uT = sum(prefixDiff[p(T, A)]) + sum(prefixDiff[p(T, C)]), 
		uC = sum(prefixDiff[p(C, T)]) + sum(prefixDiff[p(C, A)])
	;

	// cout << g(A) << " has " << uA << " unsorted. " << g(T) << " has " << uT << " unsorted. " << g(C) << " has " << uC << " unsorted.\n\n";

	int GTSwaps = min(sum(prefixDiff[p(A, T)]), sum(prefixDiff[p(T, A)]));
	int GCSwaps = min(sum(prefixDiff[p(A, C)]), sum(prefixDiff[p(C, A)]));

	// cout << "There are " << GTSwaps << " good swaps between " << g(A) << " and " << g(T) << "\n";
	// cout << "There are " << GCSwaps << " good swaps between " << g(A) << " and " << g(C) << "\n\n";

	moves += GTSwaps + GCSwaps;
	uA -= GTSwaps + GCSwaps;
	uT -= GTSwaps;
	uC -= GCSwaps;

	// cout << moves << " moves were used performing good swaps.\n";
	// cout << g(A) << " has " << uA << " unsorted. " << g(T) << " has " << uT << " unsorted. " << g(C) << " has " << uC << " unsorted.\n";

	int badT = sum(prefixDiff[p(T, A)]) - GTSwaps;
	int badC = sum(prefixDiff[p(C, A)]) - GCSwaps;

	// cout << "There are " << badT << " bad swaps between " << g(A) << " and " << g(T) << "\n";
	// cout << "There are " << badC << " bad swaps between " << g(A) << " and " << g(C) << "\n\n";

	moves += badT + badC;
	uA -= badT + badC;
	// uT += badT;
	// uC += badC;

	// cout << moves << " moves were used performing good + bad swaps.\n";
	// cout << g(A) << " has " << uA << " unsorted. " << g(T) << " has " << uT << " unsorted. " << g(C) << " has " << uC << " unsorted.\n\n";

	// cout << moves + badT << " moves were used fixing a[" << x << ":" << y << "] with order {" << g(A) << ", " << g(T) << ", " << g(C) << "}\n";
	return moves + uT;
}

int get_distance(int x, int y) {
	for (int j = 0; j < 3; j++) {
		int cntA = sum(prefixA[j]);
		int cntB = sum(prefixB[j]);

		if (cntA != cntB) return -1;
	}
	
	// cout << "a[x:y] = [" << A[x];
	// for (int i = x+1; i <= y; i++) {
	// 	cout << ", " << A[i];
	// }
	// cout << "]\n";
	// cout << "b[x:y] = [" << B[x];
	// for (int i = x+1; i <= y; i++) {
	// 	cout << ", " << B[i];
	// }
	// cout << "]\n";
	// cout << "\n";
	int ans = min({try_fix(x, y, 0, 1, 2), try_fix(x, y, 1, 0, 2), try_fix(x, y, 2, 1, 0)});
	return ans;
}

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