Submission #1228123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228123		minhpk	Genetics (BOI18_genetics)	C++20	46 / 100	2093 ms	5056 KiB

genetics

#include <bits/stdc++.h>

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<4101> t[4101];
bitset<4101> t1[4101];
bitset<4101> t2[4101];
bitset<4101> t3[4101];
int res[4101];

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

    int a, b, c;
    fast_read(a);
    fast_read(b);
    fast_read(c);

    for (int i = 1; i <= a; i++) {
        string s;
        fast_read(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;
            }else{
                t3[i][j]=1;
            }
        }
    }

    for (int i = 1; i <= a; i++) {
        for (int j = i + 1; j <= a; j++) {
            if ((t[i] ^ t[j]).count()+(t1[i] ^ t1[j]).count()+(t2[i] ^ t2[j]).count()+(t3[i] ^ t3[j]).count() == 2*c) {
                res[i]++;
                res[j]++;
            }
        }
    }

    for (int i = 1; i <= a; i++) {
        if (res[i] == a - 1) {
            cout << i << "\n";
            return 0;
        }
    }

    return 0;
}

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