Submission #853501

#	Time	Username	Problem	Language	Result	Execution time	Memory
853501		Trisanu_Das	Genetics (BOI18_genetics)	C++17	74 / 100	1025 ms	57496 KiB

genetics

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
 
int n, m, k;
string a[5000];
bitset<4105> bs[4105];
 
bool check(int x){
	for(int i = 1; i <= n; i++){
		if(i == x) continue;
		int cnt = 0;
		for(int j = 0; j < m; j++) if(a[x][j] != a[i][j]) cnt++;
		if(cnt != k) return false;
	}
	return true;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	if(n <= 100){
		for(int i = 1; i <= n; i++){
			if(check(i)){
				cout << i << '\n';
				return 0;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < m; j++){
			bs[i][j] = (a[i][j] == 'A');
			assert(a[i][j] == 'A' || a[i][j] == 'C');
		}
	}
	for(int i = 1;i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			bitset<4105> tmp = (bs[i] ^ bs[j]);
			if(tmp.count() != k) goto yourmom;
		}
		cout << i << '\n';
		return 0;
		yourmom:;
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:43:19: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    if(tmp.count() != k) goto yourmom;
      |       ~~~~~~~~~~~~^~~~

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