oj.uz

Submission #123955

# Submission time Handle Problem Language Result Execution time Memory
123955 2019-07-02T10:06:36 Z johutha Genetics (BOI18_genetics) C++14
0 / 100
 403 ms 3192 KB 
#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)1e7);

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

    vector<int> res(n, 0);

    for (int z = 0; z < N_attemps; z++)
    {
        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 f = 0; f < 4; f++)
                {
                    curr += table[j][f];
                }
                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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 403 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 403 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -