Submission #713039

#	Time	Username	Problem	Language	Result	Execution time	Memory
713039		yeyso	Mutating DNA (IOI21_dna)	C++17	35 / 100	38 ms	5952 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string s, t;
vector<int> afix;
vector<int> bfix;
vector<int> dp0;
string aa = "A";
string bb = "T";
int l = 0;
void init(string a, string b) {
	s = a;
	t = b;
	l = a.length();
	vector<int> af(a.length(), 0);
	vector<int> bf(b.length(), 0);
	vector<int> dp(a.length(), 0);
	if(a[0] != b[0]){
		dp[0] = 1;
	}
	if(a[0] == aa[0]){
		af[0] = 1;
	} else {
		//af[0] = -1;
	}
	if(b[0] == aa[0]){
		bf[0] = 1;
	} else {
		//bf[0] = -1;
	}
	for(int i = 1; i < l; i ++){
		if(a[i] != b[i]){
			dp[i] = dp[i-1] + 1;
		} else {
			dp[i] = dp[i-1];
		}

		if(a[i] == aa[0]){
			af[i] = af[i-1] + 1;
		} else {
			af[i] = af[i-1];
		}
		if(b[i] == aa[0]){
			bf[i] = bf[i-1] + 1;
		} else {
			bf[i] = bf[i-1];
		}
	}
	dp0 = dp;
	afix = af;
	bfix = bf;
}	

int get_distance(int x, int y) {
	if(x == 0){
		if(afix[y] == bfix[y]){
			return dp0[y] / 2;
		} else {
			return -1;
		}
	} else {
		if(afix[y] - afix[x-1] == bfix[y] - bfix[x-1]){
				return (dp0[y] - dp0[x-1]) / 2;
		} else {
			return -1;
		}
	}
}
/*
7 3
ATTATAT
TATATTA
0 6
0 1
3 6
*/

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