제출 #438559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438559		Stickfish	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	59 ms	7708 KiB

dna

#include "dna.h"
#include <vector>
#include <cassert>
using namespace std;

struct matrix{
	int vl[3][3];

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

	int* operator[](int i){
		return vl[i];
	}

	matrix operator-(matrix m) const {
		matrix ans;
		for(int i = 0; i < 3; ++i){
			for(int j = 0; j < 3; ++j){
				ans[i][j] = vl[i][j] - m[i][j];
			}
		}
		return ans;
	}

	int geteval(){
		int ans = 0;
		int sm[3] = {0, 0, 0};
		for(int i = 0; i < 3; ++i){
			for(int j = 0; j < 3; ++j){
				sm[i] += vl[i][j];
				sm[j] -= vl[i][j];
			}
		}
		for(int i = 0; i < 3; ++i)
			if(sm[i] != 0)
				return -1;
		for(int i = 0; i < 3; ++i){
			for(int j = i + 1; j < 3; ++j){
				int p = min(vl[i][j], vl[j][i]);
				ans += p;
				vl[i][j] -= p;
				vl[j][i] -= p;
			}
		}
		int cnt0 = 0;
		for(int j = 0; j < 3; ++j)
			cnt0 += vl[0][j];
		return ans + cnt0 * 2;
	}
};

const int MAXN = 1e5 + 123;
matrix pfm_[MAXN];
matrix* pfm = pfm_ + 1;

vector<int> cnvt(string a){
	int n = a.size();
	vector<int> ans(n);
	for(int i = 0; i < n; ++i){
		if(a[i] == 'A')
			ans[i] = 0;
		if(a[i] == 'C')
			ans[i] = 1;
		if(a[i] == 'T')
			ans[i] = 2;
	}
	return ans;
}

void init(string a_, string b_){
	vector<int> a = cnvt(a_);
	vector<int> b = cnvt(b_);
	int n = a.size();
	
	for(int i = 0; i < n; ++i){
		pfm[i] = pfm[i - 1];
		if(a[i] != b[i]){
			++pfm[i][a[i]][b[i]];
		}
	}
}

int get_distance(int x, int y) {
	++y;
	return (pfm[y - 1] - pfm[x - 1]).geteval();
}

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