Submission #1207213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207213		repsak	Mutating DNA (IOI21_dna)	C++20	0 / 100	227 ms	25616 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


vector<map<pair<char, char>, int>> values;

void init(std::string a, std::string b) {
	int N = a.size();
	values.resize(N + 1);
	
	for(int i = 0; i < N; i++){
		char A = a[i]; char B = b[i];

		values[i + 1] = values[i];
		values[i + 1][{A, B}]++;
	}
}

int get_distance(int x, int y) {
	// Create difference
	map<pair<char, char>, int> last = values[y + 1];
	map<pair<char, char>, int> first = values[x]; // might need -2?
	map<pair<char, char>, int> difference;

	vector<char> conv = {'A', 'C', 'T'};
	
	map<char, int> timesTo;
	map<char, int> timesFrom;

	for(char c : conv){
		for(auto v : conv){
			difference[{c, v}] = last[{c, v}] - first[{c, v}];
			if(difference[{c, v}] < 0) return -1;

			timesTo[v] += difference[{c, v}];
			timesFrom[c] += difference[{c, v}];
		}
	}
	
	if(timesTo.size() != timesFrom.size()) return -1;
	for(char c : conv) if(timesTo[c] != timesFrom[c]) return -1;

	int amount = 0;
	int additional = 0;
	for(char c : conv){
		for(auto v : conv){
			int in = min(difference[{c, v}], difference[{v, c}]);
			difference[{c, v}] -= in; difference[{v, c}] -= in;
			amount += in;

			int remain = max(difference[{c, v}], difference[{v, c}]);
			
			if(remain){
				int f = difference[{c, v}];
				int b = difference[{v, c}];
				additional += remain;
			}
			difference[{c, v}] = 0; difference[{v, c}] = 0;
		}
	}
	if(additional % 3 != 0) return -1; //is this true?

	return amount + (additional / 3) * 2;
}

// #include "grader.cpp"

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