Submission #1189599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189599		North1304	Mutating DNA (IOI21_dna)	C++20	100 / 100	20 ms	5028 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int N = 1e5 + 1;
int at[N] , ta[N] , ac[N] , ca[N] , tc[N] , ct[N];
void init(string a, string b) {
	int n = a.size();
	a = ' ' + a;
	b = ' ' + b;
	for (int i=1;i<=n;i++) {
		at[i] = at[i-1] + (a[i]=='A' && b[i]=='T');
		ta[i] = ta[i-1] + (a[i]=='T' && b[i]=='A');
		ac[i] = ac[i-1] + (a[i]=='A' && b[i]=='C');
		ca[i] = ca[i-1] + (a[i]=='C' && b[i]=='A');
		tc[i] = tc[i-1] + (a[i]=='T' && b[i]=='C');
		ct[i] = ct[i-1] + (a[i]=='C' && b[i]=='T');
	}
}

int get_distance(int x, int y) {
	x++;
	y++;
	int nowat = at[y] - at[x-1];
	int nowta = ta[y] - ta[x-1];
	int nowac = ac[y] - ac[x-1];
	int nowca = ca[y] - ca[x-1];
	int nowtc = tc[y] - tc[x-1];
	int nowct = ct[y] - ct[x-1];
	int minat = min(nowat, nowta);
	int minac = min(nowac, nowca);
	int mintc = min(nowtc, nowct);
	nowat -= minat;
	nowta -= minat;
	nowac -= minac;
	nowca -= minac;
	nowtc -= mintc;
	nowct -= mintc;
	if (nowat==nowtc && nowtc==nowca && nowct==nowta && nowta==nowac) return minat + minac + mintc + max(nowat, nowta) * 2;
	else return -1;
	return 0;
}

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