Submission #864404

#	Time	Username	Problem	Language	Result	Execution time	Memory
864404		iskhakkutbilim	Genetics (BOI18_genetics)	C++17	46 / 100	2053 ms	21564 KiB

genetics

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

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 4100;
bitset<N+1> bits[N+1];
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	int n, m, k; cin >> n >> m >> k;
	vector<string> a(n);
	for(auto &x : a) cin >> x;
	if(n <= 100 && m <= 100){
		for(int i = 0;i < n; i++){
			int ok = 0;
			for(int j = 0;j < n; j++){
				if(i == j) continue;
				int c = 0;
				for(int idx = 0; idx < m; idx++){
					c+= a[i][idx] != a[j][idx];
				}
				if(c != k){
					ok = 1;
					break;
				}
			}
			if(!ok){
				cout << i+1;
				return 0;
			}
		}
	}else{
		for(int i = 0;i < n; i++){
			for(int j = 0;j < m; j++){
				if(a[i][j] == 'A'){
					bits[i][j] = 1;
				}else{
					bits[i][j] = 0;
				}
			}
		}
		for(int i = 0;i < n; i++){
			int ok = 0;
			for(int j = 0;j < n; j++){
				if(i == j) continue;
				if((bits[i] ^ bits[j]).count() != k){
					ok = 1;
					break;
				}
			}
			if(!ok){
				cout << i+1;
				return 0;
			}
		}
	}
	

	return 0;
}

Compilation message (stderr)

genetics.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~
genetics.cpp: In function 'int main()':
genetics.cpp:48:36: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     if((bits[i] ^ bits[j]).count() != k){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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