Submission #825430

#	Time	Username	Problem	Language	Result	Execution time	Memory
825430		QwertyPi	Genetics (BOI18_genetics)	C++14	100 / 100	923 ms	33412 KiB

genetics

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 4100 + 11;
const int MOD = 1e9 + 7;
bitset<4100> A0[4100], A1[4100];
bitset<4100> B, B0, B1;
int f(char c){
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'T') return 3;
}

bool fail[MAXN];
int a[MAXN];
int b[MAXN][4];
char _c[MAXN][MAXN];
int32_t main(){
	random_device rd;
	mt19937 rng(rd());

	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n; i++) a[i] = rng();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			char c; cin >> c; _c[i][j] = c;
			b[j][f(c)] += a[i];
		}
	}

	for(int j = 0; j < m; j++){
		for(int k = 0; k < 4; k++){
			b[j][k] %= MOD;
		}
	}

	for(int i = 0; i < n; i++){
		int s = 0, rs = 0;
		for(int j = 0; j < n; j++){
			if(i != j) s += k * a[j];
		}
		s %= MOD;
		for(int j = 0; j < m; j++){
			for(int k = 0; k < 4; k++){
				if(k != f(_c[i][j])) rs += b[j][k];
			}
		}
		rs %= MOD;
		if(s == rs){
			cout << i + 1 << endl;
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'long long int f(char)':
genetics.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

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