Submission #395194

#	Time	Username	Problem	Language	Result	Execution time	Memory
395194		wenqi	Genetics (BOI18_genetics)	C++14	100 / 100	539 ms	33620 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

int N, M, K;

using H = uint64_t;

#define P1 30881

const H P2 = (1ll << 45) - 1;

char dna[4169][4169];

H coef[4169];

int idx[256];

uint64_t Y[6];
uint64_t E[4169];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K;

	coef[0] = 1;
	for(int i = 1; i <= N; i++) {
		cin >> dna[i];
		coef[i] = (coef[i - 1] * P1) & P2;
	}

	idx['A'] = 0;
	idx['C'] = 1;
	idx['G'] = 2;
	idx['T'] = 3;

	for(int i = 0; i < M; i++) {
		Y[0] = 0; Y[1] = 0; Y[2] = 0; Y[3] = 0;
		for(int j = 1; j <= N; j++) {
			int w = idx[dna[j][i]];
			Y[w] += coef[j];
			Y[w] &= P2;
		}

		for(int j = 1; j <= N; j++) {
			for(int ii = 0; ii < 4; ii++) {
				if(idx[dna[j][i]] != ii) {
					E[j] += Y[ii];
					E[j] &= P2;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		H needed = 0;

		for(int j = 1; j <= N; j++) {
			if(i == j) continue;
			needed = (needed + coef[j] * K) & P2;
		}

		H T = E[i];

		if(T == needed) {
			cout << i << '\n';
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:42:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    int w = idx[dna[j][i]];
      |                ~~~~~~~~^
genetics.cpp:49:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(idx[dna[j][i]] != ii) {
      |            ~~~~~~~~^

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