Submission #1093655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093655		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	260 ms	36480 KiB

genetics

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

const long long inf = 1e10;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
uniform_int_distribution<long long> D(1, inf);

string adn[4104];
unsigned long long val[4104], _hash[4104];
unsigned long long sum[256], total;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, k; cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) cin >> adn[i], val[i] = D(rng);
	for (int i = 0; i < m; ++i) {
		total = 0;
		for (int j = 1; j <= n; ++j) sum[adn[j][i]] += val[j], total += val[j];
		for (int j = 1; j <= n; ++j) _hash[j] += total - sum[adn[j][i]];
		for (int j = 1; j <= n; ++j) sum[adn[j][i]] -= val[j];
	}
	for (int i = 1; i <= n; ++i) if (_hash[i] == (total - val[i]) * k) {cout << i << '\n'; return 0;}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:20:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   for (int j = 1; j <= n; ++j) sum[adn[j][i]] += val[j], total += val[j];
      |                                             ^
genetics.cpp:21:65: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |   for (int j = 1; j <= n; ++j) _hash[j] += total - sum[adn[j][i]];
      |                                                                 ^
genetics.cpp:22:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |   for (int j = 1; j <= n; ++j) sum[adn[j][i]] -= val[j];
      |                                             ^

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