Submission #760797

#	Time	Username	Problem	Language	Result	Execution time	Memory
760797		MetalPower	Genetics (BOI18_genetics)	C++14	100 / 100	299 ms	36220 KiB

genetics

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

#define ll long long

const int MX = 4105;

int N, M, K, wt[MX]; ll sum[MX][4];
string s[MX];

int index(char c){
	if(c == 'A') return 0;
	else if(c == 'C') return 1;
	else if(c == 'G') return 2;
	else return 3;
}

random_device rd;
mt19937 rng(rd());
uniform_int_distribution<> distrib(1, 1 << 30);

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

	cin >> N >> M >> K;
	for(int i = 0; i < N; i++) cin >> s[i];

	ll tot_wt = 0;
	for(int i = 0; i < N; i++){
		wt[i] = distrib(rng);
		tot_wt += wt[i];
	}

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++) sum[j][index(s[i][j])] += wt[i];
	}

	for(int i = 0; i < N; i++){
		ll total = 0;
		for(int j = 0; j < M; j++){
			for(int k = 0; k < 4; k++){
				if(index(s[i][j]) == k) continue;
				total += sum[j][k];
			}
		}
		ll hash = 1ll * K * tot_wt - 1ll * K * wt[i];
		if(total == hash){
			cout << i + 1 << '\n';
			return 0;
		}
	}
}

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