Submission #1142007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142007		mifo	Mutating DNA (IOI21_dna)	C++20	0 / 100	1593 ms	2112 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) //vector<std::string> &path
{
	if (a==b){
		count++;
		if(count < bigger_count || bigger_count==0) bigger_count = count;
		// path.push_back(a);
		return true;
	}

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

	for(int i=0;i<tree[ind].size();i++){
		if(tree[ind][i] == par) continue;
		if(dfs(ind+1,tree[ind][i],b,a,tree,count)){
			//path.push_back(a);
			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<string> path;
	vector<vector<string>> tree(pow(f.size(), s.size()));
	int counter = 0;

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

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

	tree[0] = {ns};

	if(dfs(1,f,s,"",tree,counter)){
		// return path.size();
		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