Submission #1243340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243340		guanex	Mutating DNA (IOI21_dna)	C++20	100 / 100	24 ms	7176 KiB

dna

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

using namespace std;

int AC[100005];
int CA[100005];
int AT[100005];
int TA[100005];
int TC[100005];
int CT[100005];
int A[100005][2];
int C[100005][2];
int T[100005][2];

void init(std::string a, std::string b) {
	AC[0] = 0;
	CA[0] = 0;
	AT[0] = 0;
	TA[0] = 0;
	TC[0] = 0;
	CT[0] = 0; 
	A[0][0] = 0;
	A[0][1] = 0;
	C[0][0] = 0;
	C[0][1] = 0;
	T[0][0] = 0;
	T[0][1] = 0;
	for(int i = 0; i < (int)a.size(); ++i){
		if(i > 0){
			AC[i] = AC[i-1];
			CA[i] = CA[i-1];
			AT[i] = AT[i-1];
			TA[i] = TA[i-1];
			TC[i] = TC[i-1];
			CT[i] = CT[i-1]; 
			A[i][0] = A[i-1][0];
			C[i][0] = C[i-1][0];
			T[i][0] = T[i-1][0];
			A[i][1] = A[i-1][1];
			C[i][1] = C[i-1][1];
			T[i][1] = T[i-1][1];
		}
		if(a[i] == 'A'){
			A[i][0]++;
		}
		if(a[i] == 'C'){
			C[i][0]++;
		}
		if(a[i] == 'T'){
			T[i][0]++;
		}
		if(b[i] == 'A'){
			A[i][1]++;
		}
		if(b[i] == 'C'){
			C[i][1]++;
		}
		if(b[i] == 'T'){
			T[i][1]++;
		}
		if(a[i] == 'A' && b[i] == 'C'){
			AC[i]++;
		}
		if(a[i] == 'A' && b[i] == 'T'){
			AT[i]++;
		}
		if(a[i] == 'T' && b[i] == 'A'){
			TA[i]++;
		}
		if(a[i] == 'C' && b[i] == 'A'){
			CA[i]++;
		}
		if(a[i] == 'C' && b[i] == 'T'){
			CT[i]++;
		}
		if(a[i] == 'T' && b[i] == 'C'){
			TC[i]++;
		}

	}
}

int get_distance(int x, int y) {
	int ac = AC[y];
	int ca = CA[y];
	int at = AT[y];
	int ta = TA[y];
	int tc = TC[y];
	int ct = CT[y];
	int a = A[y][0];
	int aa = A[y][1];
	int c = C[y][0];
	int cc = C[y][1];
	int t = T[y][0];
	int tt = T[y][1];
	if(x > 0){
		ac -= AC[x-1];
		ca -= CA[x-1];
		at -= AT[x-1];
		ta -= TA[x-1];
		tc -= TC[x-1];
		ct -= CT[x-1];
		a -= A[x-1][0];
		aa -= A[x-1][1];
		c -= C[x-1][0];
		cc -= C[x-1][1];
		t -= T[x-1][0];
		tt -= T[x-1][1];
	}
	if(t != tt || c != cc || a != aa){
		return -1;
	}
	int ans = 0;
	if(ac > ca){
		swap(ca, ac); //ac is min
	}
	if(at > ta){
		swap(at, ta); // at is min
	}
	if(tc > ct){
		swap(tc, ct); //tc is min
	}
	ans += ac;
	ans += at;
	ans += tc;
	ca -= ac;//substract mins
	ta -= at;
	ct -= tc;
	ans += 2 * ct;
	return ans;
}

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