Submission #540321

#	Time	Username	Problem	Language	Result	Execution time	Memory
540321		skittles1412	Genetics (BOI18_genetics)	C++17	74 / 100	2064 ms	58264 KiB

genetics

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

#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

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

const int maxn = 4105;

int n, m, k;
char arr[maxn][maxn];

namespace s1 {

const string chars = "ACGT";
const long mod = 1e9 + 7;
bitset<maxn> arrb[maxn][4];

long hsh(int ind) {
	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;
}

void solve() {
	mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
	int ord[n], conv[n];
	bool bad[n] {}, checked[n][n] {};
	iota(ord, ord + n, 0);
	shuffle(ord, ord + n, cowng);
	int cind = 0;
	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++;
	}
	dbg(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 cnt = 0;
			for (int a = 0; a < 4; a++) {
				cnt += int((arrb[i][a] ^ arrb[j][a]).count());
				if (cnt > k) {
					break;
				}
			}
			checked[i][j] = checked[j][i] = true;
			if (cnt != k) {
				bad[j] = true;
				goto loop;
			}
		}
		cout << conv[i] + 1 << endl;
		return;
	loop:;
	}
}

}  // namespace s1

namespace s2 {

const int maxb = maxn;

bitset<maxb> arrb[maxb];

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 'A') {
				arrb[i].set(j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i != j) {
				int cnt = int((arrb[i] ^ arrb[j]).count());
				if (cnt != k) {
					goto loop;
				}
			}
		}
		cout << i + 1 << endl;
		return;
	loop:;
	}
}

}  // namespace s2

void solve() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	bool b = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b &= arr[i][j] == 'A' || arr[i][j] == 'C';
		}
	}
	if (b) {
		s2::solve();
	} else {
		s1::solve();
	}
}

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: 0 / 26