Submission #1267200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267200		canhnam357	Genetics (BOI18_genetics)	C++20	100 / 100	110 ms	20120 KiB

genetics

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int unsigned long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<string> a(n);
	string DNA = "ACGT";
	for (string &s : a)
	{
		cin >> s;
		for (char &c : s)
		{
			c = (char)('0' + DNA.find(c));
		}
	}
	vector<int> hash_val(n);
	int tot_row = 0, row = 0;
	for (int &i : hash_val) 
	{
		i = mt();
		row += i;
		tot_row += i * m;
	}
	vector<vector<int>> hash_col(m, vector<int>(4));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			hash_col[j][a[i][j] - '0'] += hash_val[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		int tot = tot_row;
		for (int j = 0; j < m; j++)
		{
			tot -= hash_col[j][a[i][j] - '0'];
		}
		if (tot == (row - hash_val[i]) * k)
		{
			cout << i + 1;
			return 0;
		}
	}
	return 0;
}

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