Submission #784846

#	Time	Username	Problem	Language	Result	Execution time	Memory
784846		mindiyak	Mutating DNA (IOI21_dna)	C++17	100 / 100	62 ms	9736 KiB

dna

#include "dna.h"
#include <vector>
#include <algorithm>
#include <set>
#include <bits/stdc++.h>
#define pb push_back
const int MAXN = 1e5 + 5;

using namespace std;

int chartoint(char a){
	if(a == 'A'){
		return 0;
	}else if(a == 'C'){
		return 1;
	}
	return 2;
}

int makeset(int a,int b){
	unordered_map<int,int> tointmap = {{0,0},{1,1},{2,2},{10,3},{11,4},{12,5},{20,6},{21,7},{22,8}}; 
	return tointmap[(a*10 + b)];
}

int Counter[9][MAXN];
int A_counter[3][MAXN],B_counter[3][MAXN];
int N;
// vector<int> A;
// vector<int> B;
// vector<int> A_B;

void init(string a, string b) {
	N = a.size();

	int _cont[9] = {0,0,0,0,0,0,0,0,0};
	int _a_cont[3] = {0,0,0};
	int _b_cont[3] = {0,0,0};

	for(int i=0;i<N;i++){
		int charval_a = chartoint(a[i]);
		int charval_b = chartoint(b[i]);
		int charval_set = makeset(charval_a,charval_b);
		// A.pb(charval_a);
		// B.pb(charval_b);
		_cont[charval_set]++;
		_a_cont[charval_a]++;
		_b_cont[charval_b]++;
 
		for(int j=0;j<3;j++){
			A_counter[j][i] = _a_cont[j];
			B_counter[j][i] = _b_cont[j];
		}
		for(int j=0;j<9;j++){
			Counter[j][i] = _cont[j];
		}
	}

	// cout << "A " << endl;
	// for(int i=0;i<N;i++){
	// 	cout << i << " -> ";
	// 	for(int j=0;j<3;j++){
	// 		cout << A_counter[j][i] << " ";
	// 	}cout << endl;
	// }

	// cout << "B " << endl;
	// for(int i=0;i<N;i++){
	// 	cout << i << " -> ";
	// 	for(int j=0;j<3;j++){
	// 		cout << B_counter[j][i] << " ";
	// 	}cout << endl;
	// }
	// cout << endl;
}

int get_count(int arr[9][MAXN],int x,int y,int pos){
	return (arr[pos][y]-arr[pos][x-1]);
}

int get_distance(int x, int y) {
	for(int j=0;j<3;j++){
		// cout << j << " " << (A_counter[j][y]-A_counter[j][x-1]) << " " << (B_counter[j][y]-B_counter[j][x-1]) << endl;
		if(get_count(A_counter,x,y,j) != get_count(B_counter,x,y,j)){
			return -1;
		}
	}

	int ans = 0;
	int setCounter[9];
	int sum = 0;

	for(int j=0;j<9;j++){
		setCounter[j] = get_count(Counter,x,y,j);
	}

	// setCounter[0] = 0;
	// setCounter[4] = 0;
	// setCounter[8] = 0;

	int _set = min(setCounter[1],setCounter[3]);//01,10
	ans += _set;
	sum += abs(setCounter[1]-setCounter[3]);

	_set = min(setCounter[2],setCounter[6]);//02,20
	ans += _set;
	setCounter[2] -= _set;
	setCounter[6] -= _set;
	sum += abs(setCounter[2]-setCounter[6]);

	_set = min(setCounter[5],setCounter[7]);//12,21
	ans += _set;
	setCounter[5] -= _set;
	setCounter[7] -= _set;
	sum += abs(setCounter[5]-setCounter[7]);

	sum /= 3;
	sum *= 2;
	ans += sum;

	return ans;
}

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