Submission #864405

#	Time	Username	Problem	Language	Result	Execution time	Memory
864405		iskhakkutbilim	Genetics (BOI18_genetics)	C++17	74 / 100	1693 ms	104276 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];
int used[N+1][N+1];
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   memset(used, -1, sizeof(used));
	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;
				int c = -1;
				if(used[i][j] != -1) c = used[i][j];
				else if(used[j][i] != -1) c = used[j][i];
				else c = (bits[i] ^ bits[j]).count();
				used[i][j] = used[j][i] = c; 
				if(c != k){
					ok = 1;
					break;
				}
			}
			if(!ok){
				cout << i+1;
				return 0;
			}
		}
	}
	

	return 0;
}

Compilation message (stderr)

genetics.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~

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