Submission #531468

#	Time	Username	Problem	Language	Result	Execution time	Memory
531468		yutabi	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	6220 KiB

dna

#include "dna.h"

int preTC[100007];
int preCT[100007];
int preTA[100007];
int preAT[100007];
int preAC[100007];
int preCA[100007];



void init(std::string a, std::string b)
{
	for(int i=0;i<a.size();i++)
	{
		preTC[i+1]=preTC[i];
		preCT[i+1]=preCT[i];
		preTA[i+1]=preTA[i];
		preAT[i+1]=preAT[i];
		preAC[i+1]=preAC[i];
		preCA[i+1]=preCA[i];
		
		if(a[i]=='T' && b[i]=='C')
		{
			preTC[i+1]++;
		}

		if(a[i]=='T' && b[i]=='A')
		{
			preTA[i+1]++;
		}

		if(a[i]=='A' && b[i]=='C')
		{
			preAC[i+1]++;
		}

		if(a[i]=='C' && b[i]=='T')
		{
			preCT[i+1]++;
		}

		if(a[i]=='A' && b[i]=='T')
		{
			preAT[i+1]++;
		}

		if(a[i]=='C' && b[i]=='A')
		{
			preCA[i+1]++;
		}
	}
}

int get_distance(int x, int y)
{
	int ans=0;

	int TC=preTC[y+1]-preTC[x];
	int CT=preCT[y+1]-preCT[x];
	int TA=preTA[y+1]-preTA[x];
	int AT=preAT[y+1]-preAT[x];
	int AC=preAC[y+1]-preAC[x];
	int CA=preCA[y+1]-preCA[x];

	int mini;

	mini=std::min(TC,CT);
	ans+=mini;
	TC-=mini;
	CT-=mini;

	mini=std::min(TA,AT);
	ans+=mini;
	TA-=mini;
	AT-=mini;

	mini=std::min(AC,CA);
	ans+=mini;
	AC-=mini;
	CA-=mini;

	mini=std::min(std::min(AT,TC),CA);
	ans+=2*mini;
	AT-=mini;
	TC-=mini;
	CA-=mini;

	mini=std::min(std::min(TA,CT),AC);
	ans+=2*mini;
	TA-=mini;
	CT-=mini;
	AC-=mini;

	if(AC || CA || AT || TA || TC || CT)
	{
		ans=-1;
	}

	return ans;
}

Compilation message (stderr)

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

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