Submission #66598

#	Time	Username	Problem	Language	Result	Execution time	Memory
66598		Bruteforceman	Genetics (BOI18_genetics)	C++11	100 / 100	1621 ms	9976 KiB

genetics

#include "bits/stdc++.h"
using namespace std;
bitset <4105> P[4][4105];
char s[4105];
int cnt[4][4105];

int main(int argc, char const *argv[])
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < n; i++) {
		scanf("%s", s);
		for(int j = 0; j < m; j++) {
			if(s[j] == 'A') {
				P[0][i][j] = 1;
				++cnt[0][j];
			}
			else if (s[j] == 'C') {
				P[1][i][j] = 1;
				++cnt[1][j];
			} else if (s[j] == 'T') {
				P[2][i][j] = 1;
				++cnt[2][j];
			} else {
				P[3][i][j] = 1;
				++cnt[3][j];
			}
		}
	}
	vector <int> v;
	for(int i = 0; i < n; i++) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int x = 0; x < n; x++) {
		bool bad = false;
		int i = v[x];

		int sum = 0;
		for(int y = 0; y < m; y++) {
			if(P[0][i][y] == 1) {
				sum += n - cnt[0][y];
			} else if (P[1][i][y] == 1) { 
				sum += n - cnt[1][y];
			} else if (P[2][i][y] == 1) {
				sum += n - cnt[2][y];
			} else {
				sum += n - cnt[3][y];
			}
		}
		if(sum != (n - 1) * k) continue;
		for(int y = 0; y < n; y++) {
			int j = v[y];
			if(i == j) continue;
			int X = (P[0][i] & P[0][j]).count() +  (P[1][i] & P[1][j]).count() +  (P[2][i] & P[2][j]).count() +  (P[3][i] & P[3][j]).count();
			if((m - X) != k) {
				bad = true;
				break;
			}
		}
		if(!bad) {
			printf("%d\n", i+1);
			exit(0);
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main(int, const char**)':
genetics.cpp:10: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:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

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