Submission #806573

#	Time	Username	Problem	Language	Result	Execution time	Memory
806573		nemethm	Mutating DNA (IOI21_dna)	C++17	56 / 100	35 ms	6032 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};

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];
		if(s1[i] != s2[i]){
			string q;
			q.push_back(s1[i]); q.push_back(s2[i]);
			sort(begin(q), end(q));
			if(q == "AT"){
				++at[i + 1];
			}
			if(q == "AC"){
				++ac[i + 1];
			}
			if(q == "CT"){
				++tc[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)){
		ll sol = sum2(x, y, at) / 2 + sum2(x, y, ac) / 2 + sum2(x, y, tc) / 2;
		if(sum2(x, y, at) % 2 == 1){
			sol += 2;
		}
		return sol;
	}
	return -1;
}

Compilation message (stderr)

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

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