Submission #1135711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135711		xnqs	Genetics (BOI18_genetics)	C++20	100 / 100	1810 ms	84760 KiB

genetics

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <bitset>

const int MAX_DIM = 4100;

int x, y, tgt;
char str[MAX_DIM][4101];
int d[MAX_DIM][MAX_DIM];
std::bitset<MAX_DIM> bs[MAX_DIM];

inline int dist(std::bitset<MAX_DIM>& a, std::bitset<MAX_DIM>& b) {
	a ^= b;
	int ret = a.count();
	a ^= b;
	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> y >> tgt;
	for (int i = 0; i < x; i++) {
		std::cin >> str[i];
	}

	for (auto ch : {'A', 'T', 'G', 'C'}) {
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				bs[i][j] = (str[i][j]==ch);
			}
		}

		for (int i = 0; i < x; i++) {
			for (int j = 0; j < i; j++) {
				int add = dist(bs[i],bs[j]);
				d[i][j] += add;
				d[j][i] += add;
			}
		}
	}

	for (int i = 0; i < x; i++) {
		bool ok = 1;
		for (int j = 0; j < x; j++) {
			if (i==j) {
				continue;
			}

			if ((d[i][j]>>1)!=tgt) {
				ok = 0;
			}
		}

		if (ok) {
			std::cout << i+1 << "\n";
			return 0;
		}
	}
}

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