Submission #59603

#	Time	Username	Problem	Language	Result	Execution time	Memory
59603		IvanC	Genetics (BOI18_genetics)	C++17	100 / 100	1345 ms	66680 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
typedef bitset<4101> bt;

const int MAXN = 4101;

bt matriz[MAXN][4],temporario;
char entrada[MAXN];
int N,M,K,marcado[MAXN],jafoi[MAXN][MAXN],somatorio[MAXN][4];

knuth_b gen(1337);
int func(int i){
	return gen() % i;
}

int main(){
	scanf("%d %d %d",&N,&M,&K);
	K = M - K;
	int LIM = 2;
	vector<int> permutacao;
	for(int i = 1;i<=N;i++){
		permutacao.push_back(i);
		scanf("%s",entrada);
		for(int j = 0;j<M;j++){
			if(entrada[j] == 'A'){
				matriz[i][0].set(j);
				somatorio[j][0]++;
			}
			else if(entrada[j] == 'C'){
				matriz[i][1].set(j);
				somatorio[j][1]++;
			}
			else if(entrada[j] == 'T'){
				matriz[i][2].set(j);
				somatorio[j][2]++;
				LIM = 4;
			}
			else{
				matriz[i][3].set(j);
				somatorio[j][3]++;
				LIM = 4;
			}
		}
	}
	random_shuffle(permutacao.begin(),permutacao.end(),func);
	for(int v : permutacao){
		if(marcado[v]) continue;
		int flag = 0;
		int total = 0;
		for(int i = 0;i<M;i++){
			for(int j = 0;j<4;j++){
				if(matriz[v][j].test(i)){
					total += somatorio[i][j];
					break;
				}
			}
		}
		total -= M;
		if((N-1)*K != total) continue;
		for(int u : permutacao){
			if(u == v || jafoi[u][v]) continue;
			jafoi[u][v] = jafoi[v][u] = 1;
			int qtd = 0;
			for(int i = 0;i<LIM;i++){
				temporario = matriz[u][i] & matriz[v][i];
				qtd += temporario.count();
			}
			if(qtd != K){
				marcado[u] = 1;
				marcado[v] = 1;
				flag = 1;
				break;
			}
		}
		if(!flag){
			printf("%d\n",v);
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
genetics.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",entrada);
   ~~~~~^~~~~~~~~~~~~~

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