Submission #1243335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243335		guanex	Mutating DNA (IOI21_dna)	C++20	35 / 100	19 ms	4876 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];

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; 
	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]; 
		}
		if(a[i] == b[i])continue;
		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];
	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];
	}
	int ans = 0;
	if(ac > ca){
		swap(ca, ac);
	}
	if(at > ta){
		swap(at, ta);
	}
	if(tc > ct){
		swap(tc, ct);
	}
	ans += ac;
	ans += at;
	ans += tc;
	ca -= ac;
	ta -= at;
	ct -= tc;
	if(ct == ta && ct == ca){
		ans += 2 * ct;
		return ans;
	}else{
		return -1;
	}
}

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