Submission #123943

#	Time	Username	Problem	Language	Result	Execution time	Memory
123943		johutha	Genetics (BOI18_genetics)	C++14	0 / 100	404 ms	3192 KiB

genetics

#include <string>
#include <iostream>
#include <random>
#include <time.h>

using namespace std;

int getchar(char c)
{
    if (c == 'A') return 0;
    else if (c == 'C') return 1;
    else if (c == 'G') return 2;
    else if (c == 'T') return 3;
}

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

    int N_attemps = 10;
    int MOD = 1e9 + 7;

    int n, m, k;
    cin >> n >> m >> k;

    mt19937 rng(time(0));
    uniform_int_distribution<int> uni(0, (int)1e9);

    vector<string> ip(n);
    for (int i = 0; i < n; i++)
    {
        cin >> ip[i];
    }

    vector<int> res(n, 0);

    for (int i = 0; i < N_attemps; i++)
    {
        int s = 0;
        vector<int> svals(n);
        for (int i = 0; i < n; i++)
        {
            svals[i] = uni(rng);
            s += svals[i];
        }
        vector<vector<int>> table(m, vector<int>(4, 0));

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                table[j][getchar(ip[i][j])] = (table[j][getchar(ip[i][j])] + svals[i]) % MOD;
            }
        }

        for (int i = 0; i < n; i++)
        {
            int ssum = 0;
            for (int j = 0; j < m; j++)
            {
                int curr = 0;
                for (int k = 0; k < 4; k++)
                {
                    curr += table[j][k];
                }
                curr -= table[j][getchar(ip[i][j])];
                ssum = (ssum + curr) % MOD;
            }
            if (ssum == ((s - svals[i])*k) % MOD) res[i]++;
        }
    }

    int mmax = -1;
    int mp = -1;

    for (int i = 0; i < n; i++)
    {
        if (res[i] > mmax)
        {
            mmax = res[i];
            mp = i;
        }
    }
    cout << mp + 1 << "\n";
}

Compilation message (stderr)

genetics.cpp: In function 'int getchar(char)':
genetics.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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