Submission #96554

#	Time	Username	Problem	Language	Result	Execution time	Memory
96554		Kastanda	Genetics (BOI18_genetics)	C++11	19 / 100	2081 ms	9976 KiB

genetics

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
using namespace std;
const int N = 4105;
int n, m, k, P[N], Q[N];
bitset < N > B[N], M[N], cant;
inline int Diff(int i, int j)
{
    return ((B[i] ^ B[j]).count());
    /*int diff = m;
    for (int w = 0; w <= 3; w ++)
        diff -= (B[i][w] & B[j][w]).count();
    return (diff);*/
}
mt19937 Rnd(chrono::steady_clock::now().time_since_epoch().count());
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    getchar();
    for (int i = 1; i <= n; i++, getchar())
    {
        for (int j = 1; j <= m; j++)
        {
            B[i][j] = (getchar() == 'A');
            /*int ch = getchar();
            if (ch == 'A') ch = 0;
            else if (ch == 'C') ch = 1;
            else if (ch == 'G') ch = 2;
            else ch = 3;
            B[i][ch][j] = 1;*/
        }
    }
    iota(P, P + n + 1, 0);
    iota(Q, Q + n + 1, 0);
    shuffle(Q + 1, Q + n + 1, Rnd);
    for (int i = 1; i <= n; i++)
    {
        int &id = Q[i];
        M[id][id] = 1;
        if (cant[id])
            continue;
        if (i % 50 == 0)
            shuffle(P + 1, P + n + 1, Rnd);
        int j = 1;
        for (; j <= n; j++)
        {
            if (!M[id][P[j]] && Diff(id, P[j]) != k)
            {
                M[id][P[j]] = M[P[j]][id] = 1;
                cant[P[j]] = 1;
                break;
            }
        }
        if (j > n)
            return !printf("%d\n", id);
    }
    assert(0);
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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