Submission #162805

#	Time	Username	Problem	Language	Result	Execution time	Memory
162805		faremy	Genetics (BOI18_genetics)	C++14	46 / 100	2127 ms	576120 KiB

genetics

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


const int MAXN = 4100;
const int MAXT = 16400;
const long long MOD = 1e14;

long long dna[MAXN][MAXT];
long long unify[MAXN][MAXN];

long long randomVector[MAXN];
long long randDna[MAXT];
long long randDiff[MAXN];
long long randUnify[MAXN];


int search(int sequences, int size)
{
	for (int iSeq = 0; iSeq < sequences; iSeq++)
		randomVector[iSeq] = (rand() * rand() * rand() * rand()) % MOD;

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

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

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		randUnify[iSeq] = 0;
		for (int jSeq = 0; jSeq < sequences; jSeq++)
			randUnify[iSeq] = (randUnify[iSeq] + unify[iSeq][jSeq] * randomVector[jSeq]) % MOD;
	}

	int answer = -1;
	for (int iSeq = 0; iSeq < sequences; iSeq++)
		if (randDiff[iSeq] == randUnify[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;

	for (int iSeq = 0; iSeq < sequences; iSeq++)
		for (int iChar = 0; iChar < size; iChar++)
		{
			char elem; std::cin >> elem;
			for (int iTrs = 0; iTrs < 4; iTrs++)
				dna[iSeq][4 * iChar + iTrs] = -1;

			switch (elem)
			{
			case 'A':
				dna[iSeq][4 * iChar] = 1;
				break;
			case 'G':
				dna[iSeq][4 * iChar + 1] = 1;
				break;
			case 'C':
				dna[iSeq][4 * iChar + 2] = 1;
				break;
			case 'T':
				dna[iSeq][4 * iChar + 3] = 1;
				break;
			}
		}

	for (int iSeq = 0; iSeq < sequences; iSeq++)
	{
		for (int jSeq = 0; jSeq < sequences; jSeq++)
			unify[iSeq][jSeq] = 4 * (size - differences);
		unify[iSeq][iSeq] = 4 * size;
	}

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

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

	return 0;
}

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