Submission #404209

#	Time	Username	Problem	Language	Result	Execution time	Memory
404209		rama_pang	Genetics (BOI18_genetics)	C++17	27 / 100	2090 ms	3412 KiB

genetics

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

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

  int N, M, K;
  cin >> N >> M >> K;

  const int MAX = 16405;
  vector<bitset<MAX>> A(N, 0);

  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < M; j++) {
      if (s[j] == 'A') A[i][j * 4 + 0] = 1;
      if (s[j] == 'C') A[i][j * 4 + 1] = 1;
      if (s[j] == 'T') A[i][j * 4 + 2] = 1;
      if (s[j] == 'G') A[i][j * 4 + 3] = 1;
    }
  }

  bitset<MAX> candidates = 0;
  for (int i = 0; i < N; i++) {
    candidates[i] = 1;
  }

  mt19937 rnd(MAX);
  vector<int> ord(N);
  iota(begin(ord), end(ord), 0);

  const int L = 40;
  while (candidates.count() > L) {
    shuffle(begin(ord), end(ord), rnd);
    for (int i = 0; i + 1 < N; i++) {
      int x = ord[i + 0];
      int y = ord[i + 1];
      int differ = (A[x] ^ A[y]).count() / 2;
      if (differ != K) {
        candidates[x] = 0;
        candidates[y] = 0;
      }
    }
  }

  vector<int> res;
  for (int i = 0; i < N; i++) {
    if (candidates[i]) {
      res.emplace_back(i);
    }
  }

  for (int x : res) {
    bool good = true;
    for (auto y : ord) if (x != y) {
      int differ = (A[x] ^ A[y]).count() / 2;
      if (differ != K) {
        good = false;
        break;
      }
    }
    if (good) {
      cout << (x + 1) << '\n';
      return 0;
    }
  }

  cout << -1 << '\n';
  return 0;
}

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