Submission #799717

#	Time	Username	Problem	Language	Result	Execution time	Memory
799717		tch1cherin	Genetics (BOI18_genetics)	C++17	100 / 100	461 ms	91736 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4.1,sse4.2,avx,avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
 
template <const int N>
struct Bitset {
  uint64_t bs[(N + 63) >> 6] = {};
 
  void set(int i) { bs[i >> 6] |= 1ull << (i & 63); }
};
 
template <const int N>
int operator^(Bitset<N>& A, Bitset<N>& B) {
  int ans = 0;
  constexpr int C = (N + 63) >> 6;
  for (int i = 0; i < C; i++) {
    ans += __builtin_popcountll(A.bs[i] ^ B.bs[i]); 
  }
  return ans;
}
 
const int MAX_N = 4105;
Bitset<MAX_N> bs[MAX_N][4];
string S[MAX_N];
bool good[MAX_N];
int dist[MAX_N][MAX_N], cnt[MAX_N][4];
int to[128];
 
using R = uniform_int_distribution<int>;
mt19937 rng(22842069);
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, K;
  cin >> N >> M >> K;
  to['A'] = 0, to['C'] = 1, to['G'] = 2, to['T'] = 3;
  int msk = 0; 
  for (int i = 0; i < N; i++) {
    cin >> S[i];
    for (int j = 0; j < M; j++) {
      cnt[j][to[S[i][j]]]++;
      bs[i][to[S[i][j]]].set(j);
      msk |= 1 << to[S[i][j]];
    }
  }
  K *= 2;
  int cand = 0;
  for (int i = 0; i < N; i++) {
    int sum = 0;
    for (int j = 0; j < M; j++) {
      sum += N - cnt[j][to[S[i][j]]];  
    }
    if (sum != (N - 1) * K / 2) {
      good[i] = false;
    } else {
      good[i] = true;
    }
    for (int it = 0; it < 200 && good[i]; it++) {
      int j = i;
      while (j == i) {
        j = R(0, N - 1)(rng);
      }
      if ((bs[i][0] ^ bs[j][0]) + (bs[i][1] ^ bs[j][1]) + (bs[i][2] ^ bs[j][2]) + (bs[i][3] ^ bs[j][3]) != K) {
        good[i] = false;
      }
    }
    cand += good[i];
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
      if (good[i] || good[j]) {
        dist[i][j] = (bs[i][0] ^ bs[j][0]) + (bs[i][1] ^ bs[j][1]) + (bs[i][2] ^ bs[j][2]) + (bs[i][3] ^ bs[j][3]);  
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (!good[i]) {
      continue;
    }
    int g = 1;
    for (int j = 0; j < i; j++) {
      g &= dist[i][j] == K; 
    }
    for (int j = i + 1; j < N; j++) {
      g &= dist[j][i] == K;
    }
    if (g) {
      cout << 1 + i << "\n";
    }
  }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:42:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |       cnt[j][to[S[i][j]]]++;
      |                        ^
genetics.cpp:43:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |       bs[i][to[S[i][j]]].set(j);
      |                       ^
genetics.cpp:44:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |       msk |= 1 << to[S[i][j]];
      |                             ^
genetics.cpp:52:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |       sum += N - cnt[j][to[S[i][j]]];
      |                                   ^

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