oj.uz

답안 #123935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123935 2019-07-02T09:53:53 Z johutha Genetics (BOI18_genetics) C++17
0 / 100
 13 ms 6264 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 = 3000;
    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(n, 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

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -