제출 #1270800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270800		cmiuc	Mutating DNA (IOI21_dna)	C++20	100 / 100	21 ms	5028 KiB

dna

#include <iostream>
// #include "dna.h"

using namespace std;
const int M = 1<<17;
int TA[M], AT[M], CA[M], AC[M], TC[M], CT[M];

void init(string a, string b){
	int n = a.size();
	
	a = '0' + a;
	b = '0' + b;

	for (int i=1;i<=n;i++){
		TA[i] = TA[i-1] + (a[i] == 'T' and b[i] == 'A');
		AT[i] = AT[i-1] + (a[i] == 'A' and b[i] == 'T');

		CA[i] = CA[i-1] + (a[i] == 'C' and b[i] == 'A');
		AC[i] = AC[i-1] + (a[i] == 'A' and b[i] == 'C');

		TC[i] = TC[i-1] + (a[i] == 'T' and b[i] == 'C');
		CT[i] = CT[i-1] + (a[i] == 'C' and b[i] == 'T');
	}
}

int get_distance(int l, int r){
	int ta = TA[r+1] - TA[l];
	int at = AT[r+1] - AT[l];
	int k = min(ta, at), ans = 0;
	ta -= k, at -= k, ans += k;

	int ca = CA[r+1] - CA[l];
	int ac = AC[r+1] - AC[l];
	k = min(ca, ac);
	ca -= k, ac -= k, ans += k;
	
	int ct = CT[r+1] - CT[l];
	int tc = TC[r+1] - TC[l];
	k = min(tc, ct);
	tc -= k, ct -= k, ans += k;

	if (ta == ac and ac == ct and at == tc and tc == ca)
		return ta * 2 + at * 2 + ans;
	return -1;
}

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