제출 #540509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540509		skittles1412	Genetics (BOI18_genetics)	C++17	100 / 100	1771 ms	61260 KiB

genetics

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse4.2,bmi2,avx2")

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

using u64 = uint64_t;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 4105, maxb = maxn / 64 + 1;
const long mod = 1e9 + 7;
const string chars = "ACGT";

struct BS {
	u64 arr[maxb];

	BS() : arr() {}

	void set(int ind) {
		arr[ind >> 6] |= u64(1) << (ind & 63);
	}

	int operator^(const BS& y) const {
		int ans = 0;
		for (int i = 0; i < maxb; i++) {
			ans += __builtin_popcountll(arr[i] ^ y.arr[i]);
		}
		return ans;
	}
};

BS arrb[maxn][4];

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	string arr[n];
	for (auto& a : arr) {
		cin >> a;
	}
	auto hsh = [&](int ind) -> long {
		long h1 = 0, h2 = 0;
		for (int i = 0; i < m; i++) {
			h1 = (h1 * 7 + int(chars.find(arr[ind][i])) + 1) % mod;
			h2 = (h2 * 11 + int(chars.find(arr[ind][i])) + 1) % mod;
		}
		return h1 * mod + h2;
	};
	mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
	int ord[n], conv[n], cind = 0;
	iota(ord, ord + n, 0);
	shuffle(ord, ord + n, cowng);
	bool bad[n] {}, checked[n][n] {};
	map<long, int> vis;
	for (auto& a : ord) {
		auto [it, inserted] = vis.emplace(hsh(a), cind);
		if (!inserted) {
			bad[it->second] = true;
			continue;
		}
		for (int c = 0; c < 4; c++) {
			for (int j = 0; j < m; j++) {
				if (arr[a][j] == chars[c]) {
					arrb[cind][c].set(j);
				}
			}
		}
		conv[cind] = a;
		cind++;
	}
	k *= 2;
	for (int i = 0; i < cind; i++) {
		if (bad[i]) {
			continue;
		}
		for (int j = 0; j < cind; j++) {
			if (i == j || checked[i][j]) {
				continue;
			}
			int cur = 0;
			for (int c = 0; c < 4; c++) {
				cur += arrb[i][c] ^ arrb[j][c];
			}
			checked[i][j] = checked[j][i] = true;
			if (cur != k) {
				bad[i] = bad[j] = true;
				goto loop;
			}
		}
		cout << conv[i] + 1 << endl;
		return;
	loop:;
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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