Submission #456405

#	Time	Username	Problem	Language	Result	Execution time	Memory
456405		nonsensenonsense1	Genetics (BOI18_genetics)	C++17	100 / 100	1490 ms	43040 KiB

genetics

#include <cstdio>
#include <algorithm>
#include <random>
#include <chrono>

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 4100;
const int K = 20;
unsigned long long a[N][(N - 1 >> 6) + 1][4];
int n, m, x, ord[N], mask[N], p[N], subset_size[K], in[K][N][4];
bool u[N][N], bad[N], inc[K][N];

int count_xor(unsigned long long (*a)[4], unsigned long long (*b)[4]) 
{
	int s = 0;
	for (int i = 0; i << 6 < m && s >> 1 <= x; ++i) {
		s += __builtin_popcountll(a[i][0] ^ b[i][0]);
		s += __builtin_popcountll(a[i][1] ^ b[i][1]);
		s += __builtin_popcountll(a[i][2] ^ b[i][2]);
		s += __builtin_popcountll(a[i][3] ^ b[i][3]);
	}
	return s >> 1;
}

void test(int p, int q) 
{
	if (u[p][q]) return;
	u[p][q] = u[q][p] = true;
	if (count_xor(a[p], a[q]) != x) bad[p] = bad[q] = 1;
}

bool subset_test(int v) 
{
	for (int i = 0; i < K; ++i) {
		int total_d = 0;
		for (int j = 0; j < m; ++j) for (int k = 0; k < 4; ++k) {
			if (a[v][j >> 6][k] >> (j & 63) & 1) total_d += subset_size[i] - in[i][j][k];
			else total_d += in[i][j][k];
		}
		if (total_d != (subset_size[i] - inc[i][v]) * x * 2) return false;
	}
	return true;
}

int main() 
{
	scanf("%d%d%d", &n, &m, &x);
	std::iota(p, p + m, 0);
	std::shuffle(p, p + m, rng);
	for (int i = 0; i < n; ++i) {
		getchar();
		for (int j = 0; j < m; ++j) {
			char ch = getchar();
			int ind;
			if (ch == 'A') ind = 0;
			else if (ch == 'C') ind = 1;
			else if (ch == 'G') ind = 2;
			else ind = 3;
			mask[i] |= 1 << ind;
			a[i][p[j] >> 6][ind] |= (unsigned long long)1 << (p[j] & 63);
		}
	}
	std::iota(ord, ord + n, 0);
	std::shuffle(ord, ord + n, rng);
	for (int i = 0; i < K; ++i) {
		for (int j = 0; j < n; ++j) if (rng() & 1) {
			++subset_size[i];
			inc[i][j] = 1;
			for (int k = 0; k < m; ++k) for (int l = 0; l < 4; ++l) in[i][k][l] += a[j][k >> 6][l] >> (k & 63) & 1;
		}
	}
	for (int i = 0; i < n; ++i) if (!bad[ord[i]] && subset_test(ord[i])) {
		for (int j = 0; j < n && !bad[ord[i]]; ++j) if (ord[j] != ord[i]) test(ord[i], ord[j]);
		if (!bad[ord[i]]) {
			printf("%d\n", ord[i] + 1);
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp:10:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   10 | unsigned long long a[N][(N - 1 >> 6) + 1][4];
      |                          ~~^~~
genetics.cpp: In function 'int main()':
genetics.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d", &n, &m, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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