Submission #654004

#	Time	Username	Problem	Language	Result	Execution time	Memory
654004		Blagoj	Mutating DNA (IOI21_dna)	C++17	56 / 100	364 ms	5580 KiB

dna

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

using namespace std;

string a, b;

bool two = false;

int dp[100009], counter[100009][3][2];

map<char, int> mp;
set<char> s;

void init(std::string a1, std::string b1) 
{
	mp['C'] = 0;
	mp['A'] = 1;
	mp['T'] = 2;
	a = a1;
	b = b1;
	if (a[0] != b[0])
	{
		dp[0] = 1;
	}
	s.insert(a[0]);
	s.insert(b[0]);
	counter[0][mp[a[0]]][0]++;
	counter[0][mp[b[0]]][1]++;
	for (int i = 1; i < a.size(); i++)
	{
		s.insert(a[i]);
		s.insert(b[i]);
		dp[i] = dp[i - 1];
		if (a[i] != b[i])
		{
			dp[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) {
	if (x == 0)
	{
		for (int i = 0; i < 3; i++)
		{
			if (counter[y][i][0] != counter[y][i][1])
			{
				return -1;
			}
		}
	}
	else
	{
		for (int i = 0; i < 3; i++)
		{
			if ((counter[y][i][0] - counter[x - 1][i][0]) != (counter[y][i][1] - counter[x - 1][i][1]))
			{
				return -1;
			}
		}
	}
	if (s.size() == 2)
	{
		if (x == 0)
		{
			return dp[y] / 2;
		}
		return (dp[y] - dp[x - 1]) / 2;
	}
	string c = a;
	int cnt = 0;
	bool possible = true;
	for (int i = x; i <= y; i++)
	{
		if (c[i] != b[i])
		{
			for (int j = i + 1; j <= y; j++)
			{
				if ((c[j] == b[i] && c[j] != b[j]) || (c[j] == b[i] && c[i] == b[j]))
				{
					swap(c[i], c[j]);
					cnt++;
					break;
				}
			}
			if (c[i] != b[i])
			{
				for (int j = i + 1; j <= y; j++)
				{
					if (c[j] == b[i] && c[j] != b[j])
					{
						swap(c[i], c[j]);
						cnt++;
						break;
					}
				}	
			}
		}
	}
	return cnt;
}

Compilation message (stderr)

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

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