Submission #1009648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009648		canadavid1	Mutating DNA (IOI21_dna)	C++17	100 / 100	29 ms	7184 KiB

dna

#include "dna.h"
#include <vector>
#include <numeric>

std::vector<int> ct[3][3];

void init(std::string a, std::string b) {
	for(auto& i : ct)
	for(auto& j : i) j = std::vector<int>(a.size()+1,0);
	for(int i = 0; i < a.size(); i++)
	{
		ct[(a[i]/2)&3][(b[i]/2)&3][i]=1;
	}
	for(auto& i : ct)
	for(auto& j : i)
	std::exclusive_scan(j.begin(),j.end(),j.begin(),0);
}

int get_distance(int x, int y) {
	y++;
	int pr[3];
	int c=0;
	for (int i = 0; i < 3; i++)
	{
		int j = (i+1)%3;	
		auto a = ct[i][j][y] - ct[i][j][x];
		auto b = ct[j][i][y] - ct[j][i][x];
		c += std::min(a,b);
		pr[i] = a-b;
	}
	if(pr[0]!=pr[1] || pr[1] != pr[2]) return -1;
	c += std::abs(2*pr[0]);
	return c;
	
}

Compilation message (stderr)

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