Submission #654009

#	Time	Username	Problem	Language	Result	Execution time	Memory
654009		Blagoj	Mutating DNA (IOI21_dna)	C++17	0 / 100	34 ms	6216 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], at[100009], ac[100009], ct[100009];

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] == 'A' || b[0] == 'A')
	{
		if (a[0] == 'C' || b[0] == 'C')
		{
			ac[0]++;
		}
		else
		{
			at[0]++;
		}
	}
	else
	{
		ct[0]++;
	}
	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++)
	{
		dp[i] = dp[i - 1];
		if (a[i] != b[i])
		{
			dp[i]++;
		}
		s.insert(a[i]);
		s.insert(b[i]);
		ac[i] = ac[i - 1];
		at[i] = at[i - 1];
		ct[i] = ct[i - 1];
		if (a[i] == 'A' || b[i] == 'A')
		{
			if (a[i] == 'C' || b[i] == 'C')
			{
				ac[i]++;
			}
			else
			{
				at[i]++;
			}
		}
		else
		{
			ct[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() == 1)
	{
		return 0;
	}
	if (s.size() == 2)
	{
		if (s.count('A') > 0)
		{
			if (s.count('C') > 0)
			{
				if (x == 0)
				{
					return ac[y] / 2;
				}
				return (ac[y] - ac[x - 1]) / 2;
			}
			else
			{
				if (x == 0)
				{
					return at[y] / 2;
				}
				return (at[y] - at[x - 1]) / 2;
			}
		}
		else
		{
			if (x == 0)
			{
				return ct[y] / 2;
			}
			return (ct[y] - ct[x - 1]) / 2;
		}
	}
	if (x == 0)
	{
		return dp[y] / 2 + dp[y] % 2;
	}
	return (dp[y] - dp[x - 1]) / 2 + (dp[y] - dp[x - 1]) % 2;
}

Compilation message (stderr)

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

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