| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 572028 | jimmaras132 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <map>
#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;
}
int main ( void ) {
init ( "ATACAT" , "ACTATA" );
printf ( "%d\n" , get_distance ( 0 , 6 ) );
return 0;
}