Submission #825411

#	Time	Username	Problem	Language	Result	Execution time	Memory
825411		QwertyPi	Genetics (BOI18_genetics)	C++14	27 / 100	2077 ms	2108 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);
		}
	}
	for(int i = 0; i < n; i++){
		if(fail[i]) continue;
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			B = A[i] ^ A[j];
			B = (B & F1) | ((B & F2) >> 1);
			if(B.count() != k){
				fail[i] = fail[j] = true;
				ok = false;
				break;
			}
		}
		if(ok){
			cout << i + 1 << endl;
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:40:17: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |    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