제출 #1272238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272238		thunopro	Mutating DNA (IOI21_dna)	C++20	100 / 100	33 ms	6128 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

int n , sum [maxn][3][3] , ch [maxn] ; 
void init( string a , string b ) {
	n = a.size() ; 
	ch ['A'] = 0 , ch ['C'] = 1 , ch ['T'] = 2 ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) 
		{
			for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) 
			{
				sum [i][t1][t2] = sum [i-1][t1][t2] ; 
			}
		}
		sum [i][ch[a[i-1]]][ch[b[i-1]]] ++ ; 
	}
}

int get_distance(int x, int y) {
	int l = x+1 , r = y+1 ; 
	int temp [3][3] = {0} ; 
	for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) temp [t1][t2] = sum [r][t1][t2] - sum [l-1][t1][t2] ; 
	
	int res = 0 ; 
	for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) 
	{
		if ( t1 == t2 ) temp [t1][t2] = 0 ; 
		else 
		{
			int c = min (temp[t1][t2],temp[t2][t1]) ; 
			temp [t1][t2] -= c , temp [t2][t1] -= c ; 
			res += c ; 
		}
	}
	for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) 
	{
		if ( t1 == t2 ) continue ; 
		int k = 3^t1^t2 ; 
		int c = min({temp[t1][t2],temp[t2][k],temp[k][t1]}) ; 
		temp [t1][t2] -= c , temp [t2][k] -= c , temp [k][t1] -= c ; 
		res += c*2 ; 
	}
	for ( int t1 = 0 ; t1 <= 2 ; t1 ++ ) for ( int t2 = 0 ; t2 <= 2 ; t2 ++ ) if ( temp [t1][t2] ) return - 1 ; 
	return res;
}

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