Submission #386749

#	Time	Username	Problem	Language	Result	Execution time	Memory
386749		maximath_1	Genetics (BOI18_genetics)	C++11	100 / 100	439 ms	36460 KiB

genetics

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 5005;
const int BLOCK = 105;
const ll inf = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1};
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

mt19937 rng(time(NULL));

int n, m, k;
string s[MX];
int wt[MX];
ll tot[MX][4];

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

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++)
		cin >> s[i];

	for(int i = 1; i <= n; i ++)
		wt[i] = rng();

	for(int i = 1; i <= n; i ++)
		for(int j = 0; j < m; j ++)
			tot[j][get(s[i][j])] += wt[i];

	for(int i = 1; i <= n; i ++){
		ll c1 = 0ll, c2 = 0ll;

		for(int j = 1; j <= n; j ++) if(i != j)
			c1 += k * 1ll * wt[j];

		for(int j = 0; j < m; j ++)
			for(int v = 0; v < 4; v ++)
				if(get(s[i][j]) != v)
					c2 += tot[j][v];

		if(c1 == c2){
			cout << i << endl;
			return 0;
		}
	}

	cout << -1 << endl;
	return 0;
}

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