Submission #1129028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129028		Ludissey	Genetics (BOI18_genetics)	C++20	19 / 100	2105 ms	306552 KiB

genetics

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int popcount_u128(__uint128_t value) {
    // Cast and split into two 64-bit halves
    uint64_t lower = (uint64_t)value;               // Lower 64 bits
    uint64_t upper = (uint64_t)(value >> 64);       // Upper 64 bits

    // Use __builtin_popcountll for each half and sum the results
    return __builtin_popcountll(lower) + __builtin_popcountll(upper);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,k; cin >> n >> m >> k;
    int blocks=(m/128)+1;
    vector<vector<__uint128_t>> a_c(n,vector<__uint128_t>(blocks+1));
    vector<vector<__uint128_t>> g_t(n,vector<__uint128_t>(blocks+1));
    for (int i = 0; i < n; i++)
    {
        int j=0;
        int bl=0;
        while(j<m){
            char c; cin >> c;
            if(c=='A') a_c[i][bl]+=((__uint128_t)1<<j);
            if(c=='T') g_t[i][bl]+=((__uint128_t)1<<j);
            j++;
            if(j%128==0) bl++;
        }
    }
    vector<vector<int>> dist(n,vector<int>(n,0));
    vector<vector<int>> dist2(n,vector<int>(n,0));
    vector<vector<int>> dist3(n,vector<int>(n,0));
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            for (int _k = 0; _k < blocks; _k++)
            {
                dist[i][j]+=popcount_u128(a_c[i][_k]^a_c[j][_k]);
                dist2[i][j]+=popcount_u128(g_t[i][_k]^g_t[j][_k]);
                dist3[i][j]+=popcount_u128(g_t[i][_k]&a_c[j][_k]);
                dist3[i][j]+=popcount_u128(a_c[i][_k]&g_t[j][_k]);
            }
            dist[j][i]=dist[i][j];
            dist2[j][i]=dist2[i][j];
            dist3[j][i]=dist3[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        bool b=true;
        for (int j = 0; j < n; j++)
        {
            if(i==j) continue;
            if((dist[i][j]+dist2[i][j])-dist3[i][j]!=k) { b=false; break; }
        }
        if(b==true){
            cout << i+1 << "\n";
            break;
        }
    }
    return 0;
}

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