제출 #438393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438393		MathMate	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	52 ms	8368 KiB

dna

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

const int MAX_N = 1e5 + 5;
const int ILOSC_LITEREK = 3;
const int ILOSC_PAR_LITEREK = 6;
const int ILOSC_NAPISOW = 2;

// A -> 0
// C -> 1
// T -> 2

vector <char> literki = {'A', 'C', 'T'};

int sumy_prefiksowe_literek[MAX_N][ILOSC_LITEREK][ILOSC_NAPISOW];

// 0 -> AC
// 1 -> CA
// 2 -> AT
// 3 -> TA
// 4 -> CT
// 5 -> TC

vector <string> pary_literek = {"AC", "CA", "AT", "TA", "CT", "TC"};

int sumy_prefiksowe_par_literek[MAX_N][ILOSC_PAR_LITEREK];

void init(string a, string b)
{
	vector <string> napisy = {a, b};

	int n = (int) a.size();

	for(int i = 0; i < ILOSC_NAPISOW; i++)
	{
		for(int j = 0; j < n; j++)
		{
			for(int literka = 0; literka < ILOSC_LITEREK; literka++)
			{
				// sumy_prefiksowe_literek[pozycja][literka][numer_napisu]

				sumy_prefiksowe_literek[j + 1][literka][i] = sumy_prefiksowe_literek[j][literka][i] + (napisy[i][j] == literki[literka]);
			}
		}
	}

	for(int i = 1; i < n; i++)
	{
		for(int para_literek = 0; para_literek < ILOSC_PAR_LITEREK; para_literek++)
		{
			string stworzona_para_literek = "";

			stworzona_para_literek += napisy[0][i];
			stworzona_para_literek += napisy[1][i];

			// sumy_prefiksowe_par_literek[pozycja][para_literek]

			sumy_prefiksowe_par_literek[i + 1][para_literek] = sumy_prefiksowe_par_literek[i][para_literek] + (stworzona_para_literek == pary_literek[para_literek]);
		}
	}
}

int get_distance(int L, int R)
{
	bool ok = true;

	for(int literka = 0; literka < ILOSC_LITEREK; literka++)
	{
		int ilosc_literek_na_przedziale_1 = sumy_prefiksowe_literek[R][literka][0] - sumy_prefiksowe_literek[L - 1][literka][0];
		int ilosc_literek_na_przedziale_2 = sumy_prefiksowe_literek[R][literka][1] - sumy_prefiksowe_literek[L - 1][literka][1];

		if(ilosc_literek_na_przedziale_1 != ilosc_literek_na_przedziale_2)
		{
			ok = false;

			break;
		}
	}

	if(ok)
	{
		int wynik = 0, do_dodania = 0;

		for(int j = 0; j < ILOSC_PAR_LITEREK / 2; j++)
		{
			int ilosc_par_literek_na_przedziale_1 = sumy_prefiksowe_par_literek[R][2 * j] - sumy_prefiksowe_par_literek[L - 1][2 * j];
			int ilosc_par_literek_na_przedziale_2 = sumy_prefiksowe_par_literek[R][2 * j + 1] - sumy_prefiksowe_par_literek[L - 1][2 * j + 1];

			wynik += min(ilosc_par_literek_na_przedziale_1, ilosc_par_literek_na_przedziale_2);

			do_dodania += abs(ilosc_par_literek_na_przedziale_1 - ilosc_par_literek_na_przedziale_2);
		}

		wynik += (do_dodania + 1) / 2 + 1;

		return wynik;
	}

	else
	{
		return -1;
	}
}

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