Submission #62881

#	Time	Username	Problem	Language	Result	Execution time	Memory
62881		IvanC	Genetics (BOI18_genetics)	C++17	100 / 100	959 ms	65528 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],somatorio1[MAXN][4],somatorio2[MAXN][4],noconjunto[MAXN];
 
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);
	random_shuffle(permutacao.begin(),permutacao.end(),func);
	for(int i = 0;i<permutacao.size()/2;i++) noconjunto[permutacao[i]] = 1;
	for(int i = 1;i<=N;i++){
		scanf("%s",entrada);
		for(int j = 0;j<M;j++){
			if(entrada[j] == 'A'){
				matriz[i][0].set(j);
				somatorio1[j][0]++;
				if(noconjunto[i]) somatorio2[j][0]++;
			}
			else if(entrada[j] == 'C'){
				matriz[i][1].set(j);
				somatorio1[j][1]++;
				if(noconjunto[i]) somatorio2[j][1]++;
			}
			else if(entrada[j] == 'T'){
				matriz[i][2].set(j);
				somatorio1[j][2]++;
				if(noconjunto[i]) somatorio2[j][2]++;
				LIM = 4;
			}
			else{
				matriz[i][3].set(j);
				somatorio1[j][3]++;
				if(noconjunto[i]) somatorio2[j][3]++;
				LIM = 4;
			}
		}
	}
	for(int v : permutacao){
		if(marcado[v]) continue;
		int flag = 0;
		int total1 = 0,total2 = 0;
		for(int i = 0;i<M;i++){
			for(int j = 0;j<4;j++){
				if(matriz[v][j].test(i)){
					total1 += somatorio1[i][j];
					total2 += somatorio2[i][j];
					break;
				}
			}
		}
		total1 -= M;
		if((N-1)*K != total1) continue;
		if(noconjunto[v]) total2 -= M;
		if(((N/2) - noconjunto[v])*K != total2) 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:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<permutacao.size()/2;i++) noconjunto[permutacao[i]] = 1;
                ~^~~~~~~~~~~~~~~~~~~~
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:25: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