Submission #456286

#	Time	Username	Problem	Language	Result	Execution time	Memory
456286		nonsensenonsense1	Genetics (BOI18_genetics)	C++17	46 / 100	2075 ms	41632 KiB

genetics

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <random>
#include <chrono>

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

const int N = 4100;
unsigned long long a[N][(N - 1 >> 6) + 1][4];
int n, m, x, ord[N], mask[N];
bool u[N][N], r[N][N];

int count_xor(unsigned long long (*a)[4], unsigned long long (*b)[4]) 
{
	int s = 0;
	for (int i = 0; i << 6 < m; ++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 / 2;
}

int count_impl(unsigned long long *a, unsigned long long *b) 
{
	int s = 0;
	for (int i = 0; i << 6 < m; ++i) s += __builtin_popcountll((a[i] | b[i]) & ~b[i]);
	return s;
}

bool test(int p, int q) 
{
	if (u[p][q]) return r[p][q];
	u[p][q] = u[q][p] = true;
	return r[p][q] = r[q][p] = count_xor(a[p], a[q]) == x;
}

int main() 
{
	scanf("%d%d%d", &n, &m, &x);
	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][j >> 6][ind] |= (unsigned long long)1 << (j & 63);
		}
	}
	std::iota(ord, ord + n, 0);
	std::shuffle(ord, ord + n, rng);
	for (int i = 0; i < n; ++i) {
		bool ok = true;
		for (int j = 0; j < n && ok; ++j) if (ord[j] != ord[i] && !test(ord[i], ord[j])) ok = false;
		if (ok) {
			printf("%d\n", ord[i] + 1);
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("Ofast")
      | 
genetics.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
genetics.cpp:13:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   13 | unsigned long long a[N][(N - 1 >> 6) + 1][4];
      |                          ~~^~~
genetics.cpp: In function 'int main()':
genetics.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d%d", &n, &m, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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