Submission #1276491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276491		rtri	Genetics (BOI18_genetics)	C++20	46 / 100	2095 ms	7768 KiB

genetics

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

int n, m, k;

int main() {
  cin.sync_with_stdio(false);
  cin >> n >> m >> k;

  vector<bitset<4100>> alines(n), glines(n), tlines(n), clines(n);
  for (int i = 0; i < n; i++) {
    string line;
    cin >> line;
    for (int j = 0; j < m; j++) {
      if (line[j] == 'A')
        alines[i][j] = 1;
      if (line[j] == 'C')
        glines[i][j] = 1;
      if (line[j] == 'T')
        tlines[i][j] = 1;
      if (line[j] == 'G')
        clines[i][j] = 1;
    }
  }

  random_device rd;
  mt19937 g(rd());

  vector<int> order(n);
  for (int i = 0; i < n; i++)
    order[i] = i;
  shuffle(order.begin(), order.end(), g);

  bitset<4100> is_good = bitset<4100>();
  for (int i = 0; i < n; i++)
    is_good[i] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int diff = (alines[order[i]] ^ alines[order[j]]).count() +
                 (glines[order[i]] ^ glines[order[j]]).count() +
                 (tlines[order[i]] ^ tlines[order[j]]).count() +
                 (clines[order[i]] ^ clines[order[j]]).count();
      if (diff / 2 != k) {
        is_good[order[i]] = 0;
        is_good[order[j]] = 0;
      }
    }
  }

  assert(is_good.count() == 1);

  cout << is_good._Find_first() + 1 << endl;
}

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