Submission #440391

#	Time	Username	Problem	Language	Result	Execution time	Memory
440391		QuantumK9	Mutating DNA (IOI21_dna)	C++17	100 / 100	214 ms	34528 KiB

dna

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

map<char,int> translator;
vector<vector<vector<int> > > operations;
vector<vector<int> > cnt[2]; 

void init(string a, string b) {

	//get n
	int n = a.length();

	//set size - 1-based index for 0 base case
	operations.resize(n+1);
	cnt[0].resize(n+1);
	cnt[1].resize(n+1);

	//set translator
	translator['A'] = 0;
	translator['T'] = 1;
	translator['C'] = 2;

	//set base cases
	cnt[0][0] = { 0, 0, 0 };
	cnt[1][0] = { 0, 0, 0 };
	operations[0] = { {0,0,0}, {0,0,0}, {0,0,0} };

	//set values
	for( int i = 0; i < n; i++ ){

		//copy previous values -- count
		cnt[0][i+1].resize(3);
		cnt[1][i+1].resize(3);

		for( int j = 0; j < 3; j++ ){
			cnt[0][i+1][j] = cnt[0][i][j];
			cnt[1][i+1][j] = cnt[1][i][j];
		}

		//set new values -- count
		cnt[0][i+1][ translator[a[i]] ]++;
		cnt[1][i+1][ translator[b[i]] ]++;

		//copy previous values -- operations
		operations[i+1].resize(3);

		for( int j = 0; j < 3; j++ ){
			operations[i+1][j].resize(3);
			for( int k = 0; k < 3; k++ ){ operations[i+1][j][k] = operations[i][j][k]; }
		}

		//set new values -- operations
		operations[i+1][ translator[a[i]] ][ translator[b[i]] ]++;
	}

	return;
}

bool possible( int x, int y ){
	int valsA, valsB;

	for( int i = 0; i < 3; i++ ){
		valsA = cnt[0][y][i] - cnt[0][x-1][i];
		valsB = cnt[1][y][i] - cnt[1][x-1][i];

		if( valsA != valsB ){ return false; }
	}
	return true;
}

int solve( int x, int y ){
	int grand = 0;

	vector<vector<int> > use;

	use.resize(3);
	for( int i = 0; i < 3; i++ ){
		use[i].resize(3);
		for( int j = 0; j < 3; j++ ){ use[i][j] = operations[y][i][j] - operations[x-1][i][j]; }
	}

	int mn = min( use[0][1], use[1][0] );
	grand += mn;
	use[0][1] -= mn; use[1][0] -= mn;

	mn = min( use[0][2], use[2][0] );
	grand += mn;
	use[0][2] -= mn; use[2][0] -= mn;

	mn = min( use[1][2], use[2][1] );
	grand += mn;
	use[1][2] -= mn; use[2][1] -= mn;

	int ttl = use[0][1] + use[1][0] + use[0][2] + use[2][0] + use[1][2] + use[2][1];
	ttl /= 3;
	ttl *= 2;

	grand += ttl;

	return grand;

}

int get_distance(int x, int y) {

	//account for 1-based indexing
	x++; y++;

	//check if possible
	if( !possible(x,y) ){ return -1; } 

	//return ans
	return solve(x,y);

	return 0;
}

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