Submission #878280

#	Time	Username	Problem	Language	Result	Execution time	Memory
878280		vjudge1	Genetics (BOI18_genetics)	C++17	46 / 100	2017 ms	77596 KiB

genetics

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

const int N = 4100 + 1;

int n, m, k, cnt[N], diff[N][N];
char c[] = {'A', 'C', 'G', 'T'};
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];
    for (int l = 0; l < 4; l++) {
        for (int i = 0; i < n; i++) {
            a[i].reset();
            for (int j = 0; j < m; j++)
                if (s[i][j] == c[l]) a[i][j] = 1;
        }
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (diff[i][j] <= 2 * k) diff[i][j] += (a[i] ^ a[j]).count();
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (diff[i][j] == 2 * 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:5: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    5 | #pragma gcc optimize("Ofast")
      | 
genetics.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization("Ofast")
      | 
genetics.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    7 | #pragma optimize(Ofast)
      | 
genetics.cpp:4:37: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize(" unroll-loops")
      |                                     ^
genetics.cpp:17:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   17 | int main() {
      |          ^
genetics.cpp: In function 'int main()':
genetics.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   34 |     for (int i = 0; i < n; i++)
      |     ^~~
genetics.cpp:39:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  return 0;
      |  ^~~~~~

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