Submission #527672

#	Time	Username	Problem	Language	Result	Execution time	Memory
527672		vivaan_gupta	Mutating DNA (IOI21_dna)	C++17	56 / 100	38 ms	10052 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];
int all[N][3][3], all2[N][3][3];



void init(std::string a, std::string b) {
	A = a, B = b;
	mp['A'] = 0;
	mp['C'] = 1;
	mp['T'] = 2;
	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];
			}
		}	

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

		all[i][tmp][tmp2] ++;
		if(i > 0){
			for(int j = 0;j< 3;j++){
				for(int k =0;k<3;k++){
					all[i][j][k] += all[i-1][j][k];
				}
			}
		}

	}
	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];
	int left = sum;
	sum = 0;
	for(int a = 0;a < 3;a++){
		for(int b = a + 1;b < 3;b++){
			// a b
			// b a
			int tmp1 = all[y][a][b];
			int tmp2 = all[y][b][a];
			if(x > 0){
				tmp1 -= all[x - 1][a][b];
				tmp2 -= all[x - 1][b][a];
			}
			left -= min(tmp1, tmp2) * 2;
			sum += min(tmp1, tmp2);
		}
	}

	return sum + max((int)0, left - 1);
}

Compilation message (stderr)

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

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