Submission #169765

#	Time	Username	Problem	Language	Result	Execution time	Memory
169765		AlexPop28	Genetics (BOI18_genetics)	C++11	100 / 100	447 ms	21496 KiB

genetics

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

int GetChar(char c) {
  return (c == 'A') * 0 + 
         (c == 'C') * 1 +
         (c == 'G') * 2 +
         (c == 'T') * 3;
}

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

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int n, m, k; cin >> n >> m >> k; cin.get();
  vector<vector<long long>> sum(m, vector<long long>(4));
  vector<string> v(n);
  vector<int> val(n);
  long long total_val = 0;
  for (int i = 0; i < n; ++i) {
    getline(cin, v[i]);
    val[i] = rng();
    total_val += val[i];
    for (int j = 0; j < m; ++j) {
      sum[j][GetChar(v[i][j])] += val[i];
    }
  }
  for (int i = 0; i < n; ++i) {
    long long hash = 0;
    for (int j = 0; j < m; ++j) {
      for (int c = 0; c < 4; ++c) {
        if (c == GetChar(v[i][j])) continue;
        hash += sum[j][c];
      }
    }
    if (hash == 1LL * k * (total_val - val[i])) {
      cout << 1 + i << endl;
      return 0;
    }
  }
}

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