Submission #1135717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135717		xnqs	Genetics (BOI18_genetics)	C++20	100 / 100	1700 ms	90916 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<4*MAX_DIM> bs[MAX_DIM];

inline int get_index(char ch) {
	if (ch=='A') return 0;
	if (ch=='T') return 1;
	if (ch=='C') return 2;
	if (ch=='G') return 3;
	return -1;
}

inline int dist(std::bitset<4*MAX_DIM>& a, std::bitset<4*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 (int j = 0; j < y; j++) {
			bs[i][4*j+get_index(str[i][j])] = 1;
		}
	}

	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