Submission #825413

#	Time	Username	Problem	Language	Result	Execution time	Memory
825413		QwertyPi	Genetics (BOI18_genetics)	C++14	27 / 100	2037 ms	5296 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4100 + 11;

bitset<8200> A[4100];
bitset<8200> B, F1, F2;
int f(char c){
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'T') return 3;
}

bool fail[MAXN];

int32_t main(){
	random_device rd;
	mt19937 rng(rd());

	int n, m, k; cin >> n >> m >> k;
	for(int j = 0; j < m; j++){
		F1.set(j * 2, 1); F2.set(j * 2 + 1, 1);
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			char c; cin >> c;
			int x = f(c);
			A[i].set(j * 2, x % 2);
			A[i].set(j * 2 + 1, x / 2);
		}
	}

	vector<int> p(n); for(int i = 0; i < n; i++) p[i] = i;
	for(int i = 0; i < n; i++) swap(p[i], p[rng() % (i + 1)]);
	for(int i = 0; i < n; i++){
		if(fail[p[i]]) continue;
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			B = A[p[i]] ^ A[p[j]];
			B = (B & F1) | ((B & F2) >> 1);
			if(B.count() != k){
				fail[p[i]] = fail[p[j]] = true;
				ok = false;
				break;
			}
		}
		if(ok){
			cout << p[i] + 1 << endl;
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:43:17: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    if(B.count() != k){
      |       ~~~~~~~~~~^~~~
genetics.cpp: In function 'int f(char)':
genetics.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
   13 | }
      | ^

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