Submission #437818

#	Time	Username	Problem	Language	Result	Execution time	Memory
437818		aggrovector	Mutating DNA (IOI21_dna)	C++17	0 / 100	38 ms	4868 KiB

dna

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

int s[100005],aa[100005],ac[100005],at[100005],ba[100005],bc[100005],bt[100005],n,i;

void init(std::string a, std::string b) {
	n=a.length();
	for (i=0;i<n;i++) {
		if (i==0) {
			s[i]=0;
		}
		else {
			s[i]=s[i-1];
		}
		if (a[i]==b[i]) {
			s[i]++;
		}
	}
	for (i=0;i<n;i++) {
		if (i==0) {
			aa[i]=0;
			ac[i]=0;
			at[i]=0;
			ba[i]=0;
			bc[i]=0;
			bt[i]=0;
		}
		else {
			aa[i]=aa[i-1];
			ac[i]=ac[i-1];
			at[i]=at[i-1];
			ba[i]=ba[i-1];
			bc[i]=bc[i-1];
			bt[i]=bt[i-1];
		}
		if (a[i]=='A') {
			aa[i]++;
		}
		else if (a[i]=='C') {
			ac[i]++;
		}
		else if (a[i]=='T') {
			at[i]++;
		}
		if (b[i]=='A') {
			ba[i]++;
		}
		else if (b[i]=='C') {
			bc[i]++;
		}
		else if (b[i]=='T') {
			bt[i]++;
		}
	}
}

int get_distance(int x, int y) {
	if (aa[y]-aa[x-1]!=ba[y]-ba[x-1]) {
		return -1;
	}
	if (ac[y]-ac[x-1]!=bc[y]-bc[x-1]) {
		return -1;
	}
	if (at[y]-at[x-1]!=bt[y]-bt[x-1]) {
		return -1;
	}
	return (y-x+1)-(s[y]-s[x-1])-1;
}

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