Submission #542260

#	Time	Username	Problem	Language	Result	Execution time	Memory
542260		apocryphal44	Mutating DNA (IOI21_dna)	C++17	0 / 100	30 ms	2380 KiB

dna

#include<string>
//#include<iostream>
using namespace std;
string s_a, s_b;

class DNA{
	public:
		string str_{};
		int A_count{0}, T_count{0}, C_count{0};

		DNA (string a) : str_(a) {
	for (auto i: str_){
		switch((int)i){
			case 65:
				this->A_count++;
				break;
			case 67:
				this->C_count++;
				break;
			case 84:
				this->T_count++;
				break;
			default:
				throw;
		}}}

};

void init(string a, string b){
	s_a=a;
	s_b=b;

}

int get_distance(int x, int y){
	// Validity Check
	if (x>y) throw;
	if (x<0 or y <0) throw;

	// Feasible Check
	const int len{(y-x)+1};
	DNA a_sub{s_a.substr((long long unsigned int)x, (long long unsigned int)len)};
	DNA b_sub{s_b.substr((long long unsigned int)x, (long long unsigned int)len)};

	if ((a_sub.A_count != b_sub.A_count) or (a_sub.C_count != b_sub.C_count) or (a_sub.T_count != b_sub.T_count)) return -1;

	// Greedy Algorithm
	int r{0}, i{0};
	for( auto j : a_sub.str_){

		char b_i = b_sub.str_.at((long long unsigned int)i);
		if (b_i != j)
		{
			for (int k{i+1}; k<len; k++){
				if (b_sub.str_.at((long long unsigned int)k) == j)
				{
					b_sub.str_[(long long unsigned int)i] = j;
					b_sub.str_[(long long unsigned int)k] = b_i;
					r++;
					break;
				}
			}
		}
		i++;
	}
	return r;
	
}

/*
int main(){
	string str1, str2;
	int a,b;
	cin >> str1 >> str2;
	init(str1, str2);
	cin >> a >> b;
	cout << get_distance(a,b);
	return 0;
}*/

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