Submission #228592

#	Time	Username	Problem	Language	Result	Execution time	Memory
228592		Haunted_Cpp	Genetics (BOI18_genetics)	C++17	74 / 100	1448 ms	19064 KiB

genetics

#include <bits/stdc++.h>
 
#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
bitset<4101> A [4101], C [4101], T [4101], G [4101];
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  if (n <= 100) {
        k = m - k;
        for (int i = 0; i < n; i++) {
            string w;
            cin >> w;
            for (int j = 0; j < (int) w.size(); j++) {
                char to = w[j];
                if (to == 'A') A[i][j] = 1;
                if (to == 'C') C[i][j] = 1;
                if (to == 'T') T[i][j] = 1;
                if (to == 'G') G[i][j] = 1;
            }
        }
        bitset<4101> diff;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                diff = A[i] & A[j];
                diff |= C[i] & C[j];
                diff |= T[i] & T[j];
                diff |= G[i] & G[j];
                if (diff.count() != k) goto fimA;
            }
            cout << i + 1 << '\n';
            return 0;
            fimA:;
        } 
    } else {
        bitset<4101> g [4101];
        for (int i = 0; i < n; i++) {
            string w;
            cin >> w;
            for (int j = 0; j < (int) w.size(); j++) {
                char to = w[j];
                assert (to != 'T');
                assert (to != 'G');
                g[i][j] = (to == 'A');
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                bitset<4101> cur = (g[i] ^ g[j]);
                int diff = cur.count();
                if (diff != k) goto fimB;
            }
            cout << i + 1 << '\n';
            return 0;
            fimB:;
        } 
        return 0;
    }
  return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:37:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (diff.count() != k) goto fimA;
                     ~~~~~~~~~~~~~^~~~

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