Submission #527594

#	Time	Username	Problem	Language	Result	Execution time	Memory
527594		vivaan_gupta	Mutating DNA (IOI21_dna)	C++17	35 / 100	46 ms	6788 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
map<char,int> mp;

string A, B;
int cnt[N][3];
int cnt2[N][3];
int bad[N];

void init(std::string a, std::string b) {
	A = a, B = b;
	mp['A'] = 0;
	mp['C'] = 1;
	mp['T'] = 1;
	for(int i = 0;i < a.size();i++){
		int tmp = mp[a[i]];
		int gg = (a[i] != b[i]);
		cnt[i][tmp] ++;
		bad[i] = gg;
		if(i > 0){
			bad[i] += bad[i-1];
			for(int j = 0;j < 3;j++){
				cnt[i][j] += cnt[i-1][j];
			}
		}	

		tmp = mp[b[i]];
		cnt2[i][tmp] ++;
		if(i > 0){
			for(int j = 0;j < 3;j++){
				cnt2[i][j] += cnt2[i-1][j];
			}
		}	
	}
	return;
}

int get_distance(int x, int y) {

	bool ok = 1;
	for(int i = 0;i < 3;i++){
		int sum = cnt[y][i];
		if(x > 0) sum -= cnt[x - 1][i];
		
		int sum2 = cnt2[y][i];
		if(x > 0) sum2 -= cnt2[x - 1][i];
		
		ok &= (sum == sum2);
	}
	if(!ok) return -1;

	int sum = bad[y];
	if(x > 0) sum -= bad[x-1];

	return ((sum + 1) / 2);

}

Compilation message (stderr)

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

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