Submission #654021

#	Time	Username	Problem	Language	Result	Execution time	Memory
654021		Blagoj	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	10036 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
 
using namespace std;
 
string a, b;
 
int counter[100009][3][2], sum[100009][3][3];
 
unordered_map<char, int> mp;
 
void init(std::string a1, std::string b1) 
{
	mp['C'] = 0;
	mp['A'] = 1;
	mp['T'] = 2;
	a = a1;
	b = b1;
	counter[0][mp[a[0]]][0]++;
	counter[0][mp[b[0]]][1]++;
	sum[0][mp[a[0]]][mp[b[0]]]++;
	for (int i = 1; i < a.size(); i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int l = 0; l < 3; l++)
			{
				sum[i][j][l] = sum[i - 1][j][l];
			}
		}
		sum[i][mp[a[i]]][mp[b[i]]]++;
		for (int j = 0; j < 3; j++)
		{
			counter[i][j][0] = counter[i - 1][j][0];
			counter[i][j][1] = counter[i - 1][j][1];
		}
		counter[i][mp[a[i]]][0]++;
		counter[i][mp[b[i]]][1]++;
	}
}
 
int get_distance(int x, int y) {
	int m = 1;
	if (x == 0)
	{
		m = 0;
	}
	for (int i = 0; i < 3; i++)
	{
		if ((counter[y][i][0] - (counter[x - 1][i][0] * m)) != (counter[y][i][1] - (counter[x - 1][i][1] * m)))
		{
			return -1;
		}
	}
	int res1 = 0, res2 = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = i + 1; j < 3; j++)
		{
			res1 += min(sum[y][i][j] - (sum[x - 1][i][j] * m), sum[y][j][i] - (sum[x - 1][j][i] * m));
			res2 += abs((sum[y][i][j] - (sum[x - 1][i][j] * m)) - (sum[y][j][i] - (sum[x - 1][j][i] * m)));
		}
	}
	return res1 + (res2 * 2) / 3;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 1; i < a.size(); i++)
      |                  ~~^~~~~~~~~~

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