제출 #1099399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099399		vjudge1	Genetics (BOI18_genetics)	C++14	27 / 100	2087 ms	7076 KiB

genetics

// Baltic OI 2018 – Genetics
#include <bits/stdc++.h>
typedef long long LL;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
using namespace std;
const int NN = 4100 + 4;
struct Item {
  bitset<NN> B[4];
  int id;
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  LL n, m, k;
  cin >> n >> m >> k;
  vector<Item> S(n);
  string s;
  const string CS = "ACGT";
  for (int i = 0; i < n and cin >> s; i++) {
    _for(j, 0, m) S[i].B[CS.find(s[j])].set(j);
    S[i].id = i + 1;
  }

  // random_device rd;  // 创建一个随机数生成器
  // mt19937 g(rd());
  // shuffle(begin(S), end(S), g);  // 随机打乱，免得遇到极端情况(答案在最后)
  _for(i, 0, n) {
    bool ok = true;
    _for(j, 0, n) {
      if (i == j) continue;
      int d = 0;
      _for(bi, 0, 4) d += (S[i].B[bi] & S[j].B[bi]).count();  // 相等的
      if (d + k != m) {
        ok = false;
        break;
      }
    }
    if (ok) return cout << S[i].id, 0;
  }
  return 0;
}
// TLE 76
/*
std::random_device 用于获取随机种子。
std::mt19937 是一个梅森旋转算法的随机数生成器，它提供了高质量的随机数
*/

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