제출 #203473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203473		faremy	Genetics (BOI18_genetics)	C++14	100 / 100	1127 ms	543436 KiB

genetics

#include <iostream>
#include <algorithm>
#include <cstdlib>


const int MAXN = 4100;
const int MAXT = 16400;


int dna[MAXN][MAXT];
int transpose[MAXT][MAXN];

int randomVector[MAXN];
int randDna[MAXT];
int randDiff[MAXN];


int search(int sequences, int size, int diff)
{
	int sum = 0;
	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		randomVector[iSeq] = rand() * rand() * rand();
		sum += (size - diff) * randomVector[iSeq];
	}

	for (int iChar = 0; iChar < size; iChar++)
	{
		randDna[iChar] = 0;
		for (int iSeq = 0; iSeq < sequences; iSeq++)
			randDna[iChar] += transpose[iChar][iSeq] * randomVector[iSeq];
	}

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		randDiff[iSeq] = 0;
		for (int iChar = 0; iChar < size; iChar++)
			randDiff[iSeq] += dna[iSeq][iChar] * randDna[iChar];
	}

	int answer = -1;
	for (int iSeq = 0; iSeq < sequences; iSeq++)
		if (randDiff[iSeq] == sum + diff * randomVector[iSeq])
		{
			if (answer == -1)
				answer = iSeq;
			else
				return -1;
		}

	return answer;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int sequences, size, differences;
	std::cin >> sequences >> size >> differences;

	std::fill_n((int *)dna, MAXN * MAXT, -1);
	std::fill_n((int *)transpose, MAXN * MAXT, -1);

	for (int iSeq = 0; iSeq < sequences; iSeq++)
		for (int iChar = 0; iChar < size; iChar++)
		{
			char elem; std::cin >> elem;
			switch (elem)
			{
			case 'A':
				dna[iSeq][4 * iChar] = 1;
				transpose[4 * iChar][iSeq] = 1;
				break;
			case 'G':
				dna[iSeq][4 * iChar + 1] = 1;
				transpose[4 * iChar + 1][iSeq] = 1;
				break;
			case 'C':
				dna[iSeq][4 * iChar + 2] = 1;
				transpose[4 * iChar + 2][iSeq] = 1;
				break;
			case 'T':
				dna[iSeq][4 * iChar + 3] = 1;
				transpose[4 * iChar + 3][iSeq] = 1;
				break;
			}
		}

	srand(42);
	int answer = search(sequences, 4 * size, 4 * differences);

	while (answer == -1)
		answer = search(sequences, 4 * size, 4 * differences);
	std::cout << answer + 1 << '\n';

	return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26