Submission #1239399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239399		lunarecho	Mutating DNA (IOI21_dna)	C++20	35 / 100	20 ms	4932 KiB

dna

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

vector<int> prefix1, prefix2, prefix3, prefix4, prefix5;
string c,d;

void init(std::string a, std::string b) {
	c = a;
	d = b;
	int n = (int)c.size();
	prefix1.resize(n+1,0);
	prefix2.resize(n+1,0);
	prefix3.resize(n+1,0);
	prefix4.resize(n+1,0);
	prefix5.resize(n+1,0);
	for(int i=0;i<n;++i)
	{
		prefix1[i + 1] += prefix1[i];
		prefix1[i + 1] += (c[i] == 'A');
		prefix2[i + 1] += prefix2[i];
		prefix2[i + 1] += (c[i] == 'T');
		prefix3[i + 1] += prefix3[i];
		prefix3[i + 1] += (d[i] == 'A');
		prefix4[i + 1] += prefix4[i];
		prefix4[i + 1] += (d[i] == 'T');
		prefix5[i + 1] += prefix5[i];
		prefix5[i + 1] += (c[i] != d[i]);
	}
}

int get_distance(int x, int y) {
	int difff = prefix5[y + 1] - prefix5[x];
	if(difff & 1)
		return -1;
	int abc1 = prefix1[y + 1] - prefix1[x];
	int abc2 = prefix2[y + 1] - prefix2[x];
	int abc3 = prefix3[y + 1] - prefix3[x];
	int abc4 = prefix4[y + 1] - prefix4[x];
	if(abc1 != abc3 || abc2 != abc4)
			return -1;
	return difff / 2;
}

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