제출 #1315387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315387		husseinjuanda	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	49 ms	7392 KiB

dna

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

string all = "ACT";

vector<int> A;
vector<int> C;
vector<int> T;

map<pair<char, char>, vector<int>> m; 


void init(std::string a, std::string b){
	A.resize(a.size()+1);
	C.resize(a.size()+1);
	T.resize(a.size()+1);
	for(int i = 0; i < all.size(); i++){
		for(int y = 0; y < all.size(); y++){
			m[{all[i], all[y]}].resize(a.size()+1, 0);
		}
	}
	for(int i = 1; i <= a.size(); i++){
		if(a[i-1] == 'A'){
			A[i]++;
		}else if(a[i-1] == 'C'){
			C[i]++;
		}else{
			T[i]++;
		}
		if(b[i-1] == 'A'){
			A[i]--;
		}else if(b[i-1] == 'C'){
			C[i]--;
		}else{
			T[i]--;
		}
		A[i] += A[i-1];
		C[i] += C[i-1];
		T[i] += T[i-1];
		m[{a[i-1], b[i-1]}][i]++;
		for(int z = 0; z < all.size(); z++){
			for(int y = 0; y < all.size(); y++){
				m[{all[z], all[y]}][i] += m[{all[z], all[y]}][i-1];
			}
		}
	}
}

int get_distance(int x, int y){
	x++;
	y++;
	if(!(A[y] - A[x-1] == 0 && C[y] - C[x-1] == 0 && T[y] - T[x-1] == 0)){
		return -1;
	}
	int ans = 0;
	int cur = y-x+1;
	cur -= m[{'A', 'A'}][y] - m[{'A', 'A'}][x-1];
	cur -= m[{'T', 'T'}][y] - m[{'T', 'T'}][x-1];
	cur -= m[{'C', 'C'}][y] - m[{'C', 'C'}][x-1];
	for(int i = 0; i < all.size(); i++){
		for(int z = i+1; z < all.size(); z++){
			ans += min(m[{all[i], all[z]}][y] - m[{all[i], all[z]}][x-1], m[{all[z], all[i]}][y] - m[{all[z], all[i]}][x-1]);
			cur -= 2*min(m[{all[i], all[z]}][y] - m[{all[i], all[z]}][x-1], m[{all[z], all[i]}][y] - m[{all[z], all[i]}][x-1]);
		}
	}
	ans += cur/3*2;
	return ans;
}

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