Submission #437872

#	Time	Username	Problem	Language	Result	Execution time	Memory
437872		aggrovector	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	6252 KiB

dna

#include "dna.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int s[100005],ac[100005],ca[100005],at[100005],ta[100005],ct[100005],tc[100005],n,i,mac,mat,mct;

void init(std::string a, std::string b) {
	n=a.length();
	for (i=0;i<n;i++) {
		if (i==0) {
			ac[i]=0;
			ca[i]=0;
			at[i]=0;
			ta[i]=0;
			ct[i]=0;
			tc[i]=0;
		}
		else {
			ac[i]=ac[i-1];
			ca[i]=ca[i-1];
			at[i]=at[i-1];
			ta[i]=ta[i-1];
			ct[i]=ct[i-1];
			tc[i]=tc[i-1];
		}
		if (a[i]=='A') {
			if (b[i]=='C') {
				ac[i]++;
			}
			else if (b[i]=='T') {
				at[i]++;
			}
		}
		else if (a[i]=='C') {
			if (b[i]=='A') {
				ca[i]++;
			}
			else if (b[i]=='T') {
				ct[i]++;
			}
		}
		else if (a[i]=='T') {
			if (b[i]=='A') {
				ta[i]++;
			}
			else if (b[i]=='C') {
				tc[i]++;
			}
		}
	}
}

int get_distance(int x, int y) {
	if (ac[y]-ac[x-1]+at[y]-at[x-1]!=ca[y]-ca[x-1]+ta[y]-ta[x-1]) {
		return -1;
	}
	if (ca[y]-ca[x-1]+ct[y]-ct[x-1]!=ac[y]-ac[x-1]+tc[y]-tc[x-1]) {
		return -1;
	}
	if (ta[y]-ta[x-1]+tc[y]-tc[x-1]!=at[y]-at[x-1]+ct[y]-ct[x-1]) {
		return -1;
	}
	mac=min(ac[y]-ac[x-1],ca[y]-ca[x-1]);
	mat=min(at[y]-at[x-1],ta[y]-ta[x-1]);
	mct=min(ct[y]-ct[x-1],tc[y]-tc[x-1]);
	return mac+mat+mct+2*(max(ac[y]-ac[x-1],ca[y]-ca[x-1])-mac);
}

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