Submission #527589

#	Time	Username	Problem	Language	Result	Execution time	Memory
527589		vivaan_gupta	Mutating DNA (IOI21_dna)	C++17	21 / 100	1580 ms	3744 KiB

dna

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

using namespace std;
const int N = 1e5 + 5;
string A, B;
void init(std::string a, std::string b) {
	A = a, B = b;
	return;
}

int get_distance(int x, int y) {

	vector<int> v;
	vector<int> v2;

	for(int i = x;i <= y;i++){
		if(A[i] == 'A')
			v.push_back(0);
		else if(A[i] == 'C')
			v.push_back(1);
		else
			v.push_back(2);
		
		if(B[i] == 'A')
			v2.push_back(0);
		else if(B[i] == 'C')
			v2.push_back(1);
		else
			v2.push_back(2);
	}
	// for(auto x:v){
	// 	cout << x << " ";
	// }
	// cout<<"\n";
	// for(auto x:v2){
	// 	cout << x << " ";
	// }
	// cout << "\n\n";

	vector<int> o = v;
	sort(v.begin(), v.end());
	int ans = 1e9;
	do{
		int cnt = 0;
		bool ok = 1;
		for(int i = 0;i < v.size();i++){
			cnt += (o[i] != v[i]);
			ok &= (v[i] == v2[i]);
		}
		if(!ok) continue;
		ans = min(ans, ((cnt+1)/2));
	}while(next_permutation(v.begin(), v.end()));
	
	if(ans == 1e9) ans = -1;
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0;i < v.size();i++){
      |                 ~~^~~~~~~~~~

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