Submission #794614

#	Time	Username	Problem	Language	Result	Execution time	Memory
794614		mathematik	Mutating DNA (IOI21_dna)	C++17	100 / 100	79 ms	23564 KiB

dna

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

using namespace std;

const string ATC = "ATC";

vector<vector<vector<int>>> amounts;
void init(std::string a, std::string b) {
	amounts = vector<vector<vector<int>>>(a.length() + 1, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}});
	for (int i = 0; i < a.length(); i++)
	{
		amounts[i + 1] = amounts[i];
		amounts[i + 1][ATC.find(a[i])][ATC.find(b[i])]++;
	}
}

int get_distance(int x, int y) {
	vector<vector<int>> t = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			t[i][j] = amounts[y + 1][i][j] - amounts[x][i][j];
		}
	}
	
	int cost = 0;
	int c;

	for (int i = 0; i < 3; i++)
	{
		c = min(t[i][(i + 1) % 3], t[(i + 1) % 3][i]);
		t[i][(i + 1) % 3] -= c;
		t[(i + 1) % 3][i] -= c;
		cost += c;
	}
	
	c = min(t[0][1], min(t[1][2], t[2][0]));
	t[0][1] -= c;
	t[1][2] -= c;
	t[2][0] -= c;
	cost += 2 * c;

	c = min(t[0][2], min(t[2][1], t[1][0]));
	t[0][2] -= c;
	t[2][1] -= c;
	t[1][0] -= c;
	cost += 2 * c;

	return t[0][1] + t[1][0] + t[0][2] + t[2][0] + t[1][2] + t[2][1] == 0 ? cost : -1;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  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