Submission #644987

#	Time	Username	Problem	Language	Result	Execution time	Memory
644987		_martynas	Genetics (BOI18_genetics)	C++11	46 / 100	2079 ms	7672 KiB

genetics

//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 4105;

int n, m, k;
bitset<MXN> A[MXN][4];
int c_to_id[256];

void solve() {
    c_to_id['A'] = 0;
    c_to_id['C'] = 1;
    c_to_id['G'] = 2;
    c_to_id['T'] = 3;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        for(int j = 0; j < m; j++) {
            int v = c_to_id[s[j]];
            A[i][v][j] = 1;
        }
    }
    vi ok(n);
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            int cnt = 0;
            for(int c = 0; c < 4; c++) {
                cnt += (A[i][c]^A[j][c]).count();
            }
            if(cnt == 2*k) {
                ok[i]++, ok[j]++;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(ok[i] == n-1) {
            cout << i+1 << "\n";
        }
    }

}

int main() {
    FASTIO();
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

/*



*/

Compilation message (stderr)

genetics.cpp: In function 'void solve()':
genetics.cpp:39:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |             int v = c_to_id[s[j]];
      |                                 ^

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