Submission #806612

#	Time	Username	Problem	Language	Result	Execution time	Memory
806612		nemethm	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	7548 KiB

dna

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

using namespace std;
using ll = long long int;

int a[100100][2] = {0}, t[100100][2] = {0}, c[100100][2] = {0};

int at[100100] = {0}, ac[100100] = {0}, tc[100100] = {0},
	ta[100100] = {0}, ca[100100] = {0}, ct[100100] = {0};

void analyse(string& s, int p){
	for(int i = 0; i < s.size(); ++i){
		a[i + 1][p] = a[i][p];
		t[i + 1][p] = t[i][p];
		c[i + 1][p] = c[i][p];
		if(s[i] == 'A'){
			++a[i + 1][p];
		}
		if(s[i] == 'T'){
			++t[i + 1][p];
		}
		if(s[i] == 'C'){
			++c[i + 1][p];
		}
	}
}

void init(std::string s1, std::string s2) {
	analyse(s1, 0);
	analyse(s2, 1);
	for(int i = 0; i < s1.size(); ++i){
		at[i + 1] = at[i];
		ac[i + 1] = ac[i];
		tc[i + 1] = tc[i];

		ta[i + 1] = ta[i];
		ca[i + 1] = ca[i];
		ct[i + 1] = ct[i];
		if(s1[i] != s2[i]){
			if(s1[i] == 'A'){
				if(s2[i] == 'C'){
					++ac[i + 1];
				}
				else{
					++at[i + 1];
				}
			}
			if(s1[i] == 'T'){
				if(s2[i] == 'C'){
					++tc[i + 1];
				}
				else{
					++ta[i + 1];
				}
			}
			if(s1[i] == 'C'){
				if(s2[i] == 'A'){
					++ca[i + 1];
				}
				else{
					++ct[i + 1];
				}
			}
		}
	}
}

int sum(int x, int y, int t[][2], int p){
	return t[y][p] - t[x - 1][p];
}

int sum2(int x, int y, int t[]){
	return t[y] - t[x - 1];
}

int get_distance(int x, int y) {
	++x, ++y;
	if(sum(x, y, a, 0) == sum(x, y, a, 1) && sum(x, y, t, 0) == sum(x, y, t, 1) && sum(x, y, c, 0) == sum(x, y, c, 1)){
		int excess = abs(sum2(x, y, ac) - sum2(x, y, ca)) + abs(sum2(x, y, at) - sum2(x, y, ta)) + abs(sum2(x, y, ct) - sum2(x, y, tc));
		int sol = min(sum2(x, y, ac), sum2(x, y, ca)) + min(sum2(x, y, at), sum2(x, y, ta)) + min(sum2(x, y, ct), sum2(x, y, tc));
		sol += excess * 2 / 3;
		return sol;
	}
	return -1;
}

Compilation message (stderr)

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

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