Submission #1135706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135706		xnqs	Genetics (BOI18_genetics)	C++20	27 / 100	2097 ms	28380 KiB

genetics

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

#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', 'C', 'T', 'G'}) {
		//std::cout << ch << "\n";
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				bs[i][j] = (str[i][j]==ch);
			}
			//std::cout << bs[i] << "\n";
		}

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

				d[i][j] += dist(bs[i],bs[j]);
			}
		}
		//std::cout << "\n";
	}

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

			//std::cout << d[i][j] << " ";
			if ((d[i][j]>>1)!=tgt) {
				ok = 0;
			}
		}
		//std::cout << "\n";

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

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