제출 #1239402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239402		lunarecho	DNA 돌연변이 (IOI21_dna)	C++20	0 / 100	19 ms	4416 KiB

dna

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

vector<int> prefix1, prefix2, prefix3, prefix4, prefix5;
string c,d;

void init(std::string a, std::string b) {
	c = a;
	d = b;
	int n = (int)c.size();
	prefix1.resize(n+1,0);
	prefix2.resize(n+1,0);
	prefix3.resize(n+1,0);
	prefix4.resize(n+1,0);
	prefix5.resize(n+1,0);
	for(int i=0;i<n;++i)
	{
		prefix1[i + 1] += prefix1[i];
		prefix1[i + 1] += (c[i] == 'A');
		prefix2[i + 1] += prefix2[i];
		prefix2[i + 1] += (c[i] == 'T');
		prefix3[i + 1] += prefix3[i];
		prefix3[i + 1] += (d[i] == 'A');
		prefix4[i + 1] += prefix4[i];
		prefix4[i + 1] += (d[i] == 'T');
		prefix5[i + 1] += prefix5[i];
		prefix5[i + 1] += (c[i] != d[i]);
	}
}

int get_distance(int x, int y) {
	if(y - x <= 2)
	{
		if(y - x == 0)
		{
			return c[x] == d[x] ? 0 : -1;
		}
		else if(y - x == 1)
		{
			if(c[x] == d[x] && c[y] == d[y])
				return 0;
			if(c[x + 1] == d[x] && c[x] == d[x + 1])
				return 1;
			return -1;
		}
		else
		{
			int a1 = 0, b1 = 0, c1 = 0;
			for(int i=x;i<y;++i)
			{
				a1 += (c[i] == 'A');
				b1 += (c[i] == 'T');
				a1 += (c[i] == 'C');
			}
			int d1 = 0, e1 = 0, f1 = 0;
			for(int i=x;i<y;++i)
			{
				d1 += (d[i] == 'A');
				e1 += (d[i] == 'T');
				f1 += (d[i] == 'C');
			}
			if(a1 != d1 || b1 != e1 || c1 != f1)
				return -1;
			int diff = 0;
			for(int i=x;i<y;++i)
				if(c[i] != d[i])
						++diff;
			return diff / 2;
		}
	}
	int difff = prefix5[y + 1] - prefix5[x];
	if(difff & 1)
		return -1;
	int abc1 = prefix1[y + 1] - prefix1[x];
	int abc2 = prefix2[y + 1] - prefix2[x];
	int abc3 = prefix3[y + 1] - prefix3[x];
	int abc4 = prefix4[y + 1] - prefix4[x];
	if(abc1 != abc3 || abc2 != abc4)
			return -1;
	return difff / 2;
}

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