Submission #654950

#	Time	Username	Problem	Language	Result	Execution time	Memory
654950		lunchbox1	Genetics (BOI18_genetics)	C++17	100 / 100	141 ms	36316 KiB

genetics

/*
 Genetics
 https://oj.uz/problem/view/BOI18_genetics
*/
#include <bits/stdc++.h>
#include <ext/random>
using namespace std;

const int N = 4100;

int h[256];

__gnu_cxx::sfmt19937 rng(1234);

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 h['A'] = 0, h['C'] = 1, h['G'] = 2, h['T'] = 3;
 int n, m, k; cin >> n >> m >> k;
 static string s[N];
 static long long v[N], f[N][4];
 long long u = 0;
 for (int i = 0; i < n; i++) {
  cin >> s[i], v[i] = rng(), u += v[i];
  for (int j = 0; j < m; j++) f[j][h[(int) s[i][j]]] += v[i];
 }
 for (int i = 0; i < n; i++) {
  long long t = 0;
  for (int j = 0; j < m; j++) t += f[j][h[(int) s[i][j]]] - v[i];
  if (t == 1LL * (u - v[i]) * (m - k)) {
   cout << i + 1 << '\n';
   return 0;
  }
 }
 assert(false);
 return 0;
}

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