Submission #1090375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090375		andrei_iorgulescu	Genetics (BOI18_genetics)	C++14	27 / 100	2054 ms	14636 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(8962);

int n, m, k;
char a[4105][4105];
bitset<8205> bs[4105];
bitset<4105> f0[4105], f1[4105], f2[4105], f3[4105];
bool inbuf[4105];

vector<int> cine[4105];

bool mna(int x, int y)
{
    int xx = (bs[x] ^ bs[y]).count() - (f0[x] & f1[y]).count() - (f1[x] & f0[y]).count() - (f2[x] & f3[y]).count() - (f3[x] & f2[y]).count();
    if (xx == k)
        return true;
    return false;
}

void shift_left(int j, int q)
{
    if (q == 0)
        return;
    vector<int> uf;
    for (int i = 0; i < q; i++)
        uf.push_back(cine[j][i]);
    cine[j].erase(cine[j].begin(), cine[j].begin() + q - 1);
    for (auto it : uf)
        cine[j].push_back(it);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            {
                if (a[i][j] == 'A')
                    bs[i][2 * j - 1] = bs[i][2 * j] = 0;
                else if (a[i][j] == 'C')
                    bs[i][2 * j] = 1;
                else if (a[i][j] == 'G')
                    bs[i][2 * j - 1] = 1;
                else
                    bs[i][2 * j - 1] = bs[i][2 * j] = 1;
                if (a[i][j] == 'A')
                    f0[i][j] = 1;
                if (a[i][j] == 'T')
                    f1[i][j] = 1;
                if (a[i][j] == 'C')
                    f2[i][j] = 1;
                if (a[i][j] == 'G')
                    f3[i][j] = 1;
            }
    for (int i = 1; i <= n; i++)
        cine[0].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        bool ok = true;
        for (int j = i - 1; j >= 0; j--)
        {
            if (!ok)
                break;
            for (int q = 0; q < cine[j].size(); q++)
            {
                int it = cine[j][q];
                if (it != i and !mna(i, it))
                {
                    ok = false;
                    cine[j].erase(cine[j].begin() + q);
                    cine[j + 1].push_back(it);
                    shift_left(j, q);
                    break;
                }
            }
        }
        if (ok)
        {
            cout << i;
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int q = 0; q < cine[j].size(); q++)
      |                             ~~^~~~~~~~~~~~~~~~

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