Submission #993270

#	Time	Username	Problem	Language	Result	Execution time	Memory
993270		caterpillow	Genetics (BOI18_genetics)	C++17	46 / 100	2005 ms	25064 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
const ll INF = 1e18;

const int sz = 4100;
using bs = bitset<4 * sz>;

int n, m, k, cnt[sz];
bs arr[sz];

main() {    
    int n, m, k; cin >> n >> m >> k;
    k = m - k;
    
    char c; 
    F0R (i, n) {
        F0R (j, m) {
            cin >> c;
            if (c == 'A') arr[i][j] = 1;
            else if (c == 'C') arr[i][j + sz] = 1;
            else if (c == 'T') arr[i][j + 2 * sz] = 1;
            else if (c == 'G') arr[i][j + 3 * sz] = 1;
        }
    }

    F0R (i, n) {
        ROF (j, i + 1, n) {
            int tot = (arr[i] & arr[j]).count();
            cnt[i] += tot == k;
            cnt[j] += tot == k;
        }
        if (cnt[i] == n - 1) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

Compilation message (stderr)

genetics.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main() {
      | ^~~~

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