Submission #1013590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013590		nomen_nescio	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	7448 KiB

dna

#include "dna.h"
using namespace std;

const int TAILLE_MAX = 100000;

int cumul[3][3][TAILLE_MAX];
int convertInt(char c)
{
	if (c == 'A')
		return 0;
	if (c == 'C')
		return 1;
	return 2;
}

int nbOccurences[3][3];
void init(std::string a, std::string b)
{
	for (int i = 0; i < a.length(); i++)
	{
		int n1, n2;
		n1 = convertInt(a[i]);
		n2 = convertInt(b[i]);
		if (n1 != n2)
		{
		nbOccurences[n2][n1]++;
		}
		for (int i1 = 0; i1 < 3; i1++)
		{
			for (int i2 = 0; i2 < 3; i2++)
			{
				cumul[i1][i2][i] = nbOccurences[i1][i2];
			}
		}
		
	}
}

int get_distance(int x, int y)
{
	int distance = 0;
	int difference[3][3];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (x == 0)
				difference[i][j] = cumul[i][j][y];
			else
				difference[i][j] = cumul[i][j][y] - cumul[i][j][x-1];
		}
	}

	int nbCCrees = 0, nbACrees = 0, nbTCrees = 0;	
	for (int i = 0; i < 3; i++) // dans le cas de 1 mais on en fait 2x trop
	{
		for (int j = 0; j < 3; j++)
		{
			if (i != j)
			{
				int minI = min(difference[i][j], difference[j][i]);
				distance += minI;
				difference[i][j] -= minI;
				difference[j][i] -= minI;
				if (difference[i][j] != 0)
				{
					if (i == 0)
						nbACrees -= difference[i][j];
					if (j == 0)
						nbACrees += difference[i][j];
					if (i == 1)
						nbCCrees -= difference[i][j];
					if (j == 1)
						nbCCrees += difference[i][j];
					if (i == 2)
						nbTCrees -= difference[i][j];
					if (j == 2)
						nbTCrees += difference[i][j];
				}
			}
		}
	}
	int diffAC = max(difference[0][1], difference[1][0]);
	int diffAT = max(difference[0][2], difference[2][0]);
	int diffCT = max(difference[1][2], difference[2][1]);
	if (diffAC == diffAT && diffAC == diffCT && nbACrees == 0 && nbCCrees == 0 && nbTCrees == 0)
	{
		return distance + 2*diffAC;
	}
	return -1;
}

Compilation message (stderr)

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

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