Submission #572030

#	Time	Username	Problem	Language	Result	Execution time	Memory
572030		jimmaras132	Mutating DNA (IOI21_dna)	C++17	100 / 100	79 ms	8224 KiB

dna

#include <iostream>
#include <vector>
#include <map>
#ifndef _DEBUG
#include "dna.h"
#endif

#define maxn 100005

inline int encode ( char v ) {
	switch ( v ) {
		case 'A': return 0;
		case 'T': return 1;
		case 'C': return 2;
	}
	return -1;
}

class BinaryIndexTree {
	int bit [ 2 * maxn ];
public:
	void modify ( int index , int val ) {
		index++;
		for ( ; index < maxn; index += index & ( -index ) ) {
			bit [ index ] += val;
		}
	}
	int query ( int index ) {
		index++;
		int ret = 0;
		for ( ; index > 0; index -= index & ( -index ) ) {
			ret += bit [ index ];
		}
		return ret;
	}
} B [ 9 ];

int s [ maxn ] , t [ maxn ];

void init ( std::string a , std::string b ) {
	for ( int i = 0; i < a.length ( ); i++ ) {
		s [ i ] = encode ( a [ i ] );
		t [ i ] = encode ( b [ i ] );
		B [ s [ i ] * 3 + t [ i ] ].modify ( i , 1 );
	}
}

int enc ( const char a [ 2 ] ) {
	return encode ( a [ 0 ] ) + 3 * encode ( a [ 1 ] );
}

int get_distance ( int l , int r ) {
	int type [ 9 ];
	for ( int i = 0; i < 9; i++ ) {
		type [ i ] = B [ i ].query ( r ) - B [ i ].query ( l - 1 );
	}
	if ( type [ 1 ] + type [ 2 ] != type [ 3 ] + type [ 6 ] || type [ 3 ] + type [ 5 ] != type [ 1 ] + type [ 7 ] ) {
		return -1;
	}
	type [ 0 ] = type [ 4 ] = type [ 8 ] = 0;
	int perm [ 3 ][ 2 ] = {
		{ enc ( "TA" ) , enc ( "AT" ) },
		{ enc ( "CA" ) , enc ( "AC" ) },
		{ enc ( "CT" ) , enc ( "TC" ) }
	};
	int ans = 0 , rem = 0;
	for ( int i = 0; i < 3; i++ ) {
		// get the minimum of the two.
		int val = std::min ( type [ perm [ i ][ 0 ] ] , type [ perm [ i ][ 1 ] ] );
		// remove it from both types cause we swap them.
		type [ perm [ i ][ 0 ] ] -= val;
		type [ perm [ i ][ 1 ] ] -= val;
		// we just did val swaps.
		ans += val;
		// we have that many remaining (one of them is zero at this point).
		rem += std::max ( type [ perm [ i ][ 0 ] ] , type [ perm [ i ][ 1 ] ] );
	}
	return ans + ( rem / 3 ) * 2;
}

#ifdef _DEBUG
int main ( void ) {
	init ( "ATACAT" , "ACTATA" );
	printf ( "%d\n" , get_distance ( 0 , 6 ) );
	return 0;
}
#endif

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for ( int i = 0; i < a.length ( ); i++ ) {
      |                   ~~^~~~~~~~~~~~~~

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