Submission #1257671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257671		chikien2009	Genetics (BOI18_genetics)	C++20	100 / 100	136 ms	19980 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, k, id[5000], a, b, c;
long long sum[5000][4], all, temp;
mt19937 ran(time(0));
string s[5000], t = "ATGC";

int main()
{
    setup();

    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i];
        id[i] = ran() % ((int)1e9 + 7);
        all += id[i];
        for (int j = 0; j < m; ++j)
        {
            for (int c = 0; c < 4; ++c)
            {
                sum[j][c] += (s[i][j] != t[c]) * id[i];
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        temp = 0;
        for (int j = 0; j < m; ++j)
        {
            for (int c = 0; c < 4; ++c)
            {
                temp += sum[j][c] * (s[i][j] == t[c]);
            }
        }
        if (temp == (all - id[i]) * k)
        {
            cout << i + 1;
            return 0;
        }
    }
    return 0;
}

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