Submission #1276490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276490		rtri	Genetics (BOI18_genetics)	C++20	47 / 100	1738 ms	2576 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>> lines(n);
  for (int i = 0; i < n; i++) {
    string line;
    cin >> line;
    for (int j = 0; j < m; j++) {
      if (line[j] == 'A')
        lines[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 = (lines[order[i]] ^ lines[order[j]]).count();
      if (diff != 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: 0 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 0 / 26