Submission #878240

#	Time	Username	Problem	Language	Result	Execution time	Memory
878240		vjudge1	Genetics (BOI18_genetics)	C++17	74 / 100	648 ms	35324 KiB

genetics

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

const int N = 4100 + 10;

int n, m, k, cnt[N];
string s[N];
bitset<N> a[N];

int main() {
	ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> s[i];
    if (n >= 1801) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (s[i][j] == 'C') a[i][j] = 1;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if ((a[i] ^ a[j]).count() == k) cnt[i]++, cnt[j]++;
    }
    else {
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int tmp = 0;
                for (int k = 0; k < s[i].size(); k++)
                    if (s[i][k] != s[j][k]) tmp++;
                if (tmp == k) cnt[i]++, cnt[j]++;
            }
    }
    for (int i = 0; i < n; i++)
        if (cnt[i] == n - 1) {
            cout << i + 1 << '\n';
            break;
        }
	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:22:43: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |                 if ((a[i] ^ a[j]).count() == k) cnt[i]++, cnt[j]++;
      |                     ~~~~~~~~~~~~~~~~~~~~~~^~~~
genetics.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |                 for (int k = 0; k < s[i].size(); k++)
      |                                 ~~^~~~~~~~~~~~~
genetics.cpp:33:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   33 |     for (int i = 0; i < n; i++)
      |     ^~~
genetics.cpp:38:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |  return 0;
      |  ^~~~~~

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