Submission #1142151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142151		mifo	Mutating DNA (IOI21_dna)	C++20	0 / 100	1593 ms	2348 KiB

dna

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

using namespace std;

vector<string> swap(string a, string par){
	vector<string> swaps;

	for(int i=0;i<a.size()-1;i++){
		for(int j=i+1;j<a.size();j++){
			string ye = "";
			ye = a;
			char save = a[i];
			ye[i] = a[j];
			ye[j] = save;
			if(ye==par) continue;
			swaps.push_back(ye);
		}
	}

	return swaps;
}

int bigger_count = 0;

bool dfs(int ind, std::string a, std::string b, string par, vector<vector<string>> &tree, int &count)
{
	if (a==b){
		count++;
		if(count < bigger_count || bigger_count==0) bigger_count = count;
		return true;
	}

	if (count > bigger_count && bigger_count != 0) return false;

	tree[ind] = swap(a, par);

	for(int i=0;i<tree[ind].size();i++){
		if(tree[ind][i] == par) continue;
		count++;
		if(dfs(ind+1,tree[ind][i],b,a,tree,count)){
			if(count < bigger_count || bigger_count==0) bigger_count = count;
			return true;
		}
	}
	return false;
}

bool count(string a, string b){
	int countaA=0, countaT=0, countaC=0;
	int countbA=0, countbT=0, countbC=0;
	for(int i=0;i<a.size();i++){
		if(a[i]=='A') countaA++;
		else if(a[i]=='T') countaT++;
		else if(a[i]=='C') countaC++;

		if(b[i]=='A') countbA++;
		else if(b[i]=='T') countbT++;
		else if(b[i]=='C') countbC++;
	}
	if(countaA==countbA && countaT==countbT && countaC==countbC){
		return true;
	} else{
		return false;
	}
}

string f="", s="";

void init(std::string a, std::string b) {
	f=a;
	s=b;
}

int get_distance(int x, int y) {
	vector<vector<string>> tree(pow(f.size(), s.size()));
	int counter = 0;

	string ns;
	string fs;
	for(int i=x-1;i<y;i++){
		ns += f[i];
		fs += s[i];
	}

	if(ns==fs) return 0;

	if(!count(f,s)) return -1;

	tree[0] = {ns};

	if(dfs(1,ns,fs,"",tree,counter)){
		return bigger_count-1;
	}else{
		return -1;
	}
	return 0;
}

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