Submission #1228165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228165		minhpk	Genetics (BOI18_genetics)	C++20	46 / 100	2092 ms	2592 KiB

genetics

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
using namespace std;


const int BUFFER_SIZE = 1 << 20;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;

inline char nextChar() {
    if (input_pos == input_len) {
        input_pos = 0;
        input_len = fread(input_buffer, 1, BUFFER_SIZE, stdin);
        if (input_len == 0) return EOF;
    }
    return input_buffer[input_pos++];
}

inline void fast_read(int &x) {
    x = 0;
    char c;
    bool neg = false;

    do {
        c = nextChar();
    } while (c != '-' && (c < '0' || c > '9'));

    if (c == '-') {
        neg = true;
        c = nextChar();
    }

    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = nextChar();
    }

    if (neg) x = -x;
}

inline void fast_read(string &s) {
    s.clear();
    char c;
    do {
        c = nextChar();
        if (c == EOF) return;
    } while (c == ' ' || c == '\n' || c == '\r' || c == '\t');
    for (; c != EOF && c != ' ' && c != '\n' && c != '\r' && c != '\t'; c = nextChar()) {
        s.push_back(c);
    }
}

bitset<4100> t[4101];
bitset<4100> t1[4101];
bitset<4100> t2[4101];
bitset<4100> t3[4101];
int res[4101];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c;
    cin >> a >> b >> c;

    for (int i = 1; i <= a; i++) {
        string s;
       cin >> s;

        for (int j = 0; j < b; j++) {
            if (s[j]=='A'){
                t[i][j]=1;
            }else if (s[j]=='T'){
                t1[i][j]=1;
            }else if (s[j]=='G'){
                t2[i][j]=1;
            }
        }
    }

    for (int i = 1; i <= a; i++) {
        bool check=true;
        for (int j = 1; j <= a; j++) {
            if (i==j){
                continue;
            }
            bitset<4100> mask;
            mask=(t[i]^t[j])|(t1[i]^t1[j])|(t2[i]^t2[j]);
          
            if (mask.count()!=c){
                check=false;
                break;
            }

        }
      //  cout << check << "\n";
        if (check){
            cout << i << "\n";
            return 0;
        }
    }

    return 0;
}

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