oj.uz

Submission #95838

# Submission time Handle Problem Language Result Execution time Memory
95838 2019-02-02T20:05:42 Z caesar2001 Genetics (BOI18_genetics) C++11
46 / 100
 2000 ms 791932 KB 
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

inline void transpune(const vector<vector<ll>> &v, vector<vector<ll>> &ans, int n, int m) {
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            ans[j][i] = v[i][j];
}

inline void multiply(const vector<vector<ll>> &a, const vector<ll> &b, vector<ll> &ans, int n, int m) {
    for(int i = 1; i <= n; i ++)
        for(int k = 1; k <= m; k ++)
                ans[i] += (a[i][k] * b[k]);
}

inline void add(vector<ll> &ans, const vector<ll> &a, int n) {
    for(int i = 1; i <= n; i ++)
        ans[i] += a[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

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

    vector<int> code(30, 0);
    code['A' - 'A'] = 1;
    code['C' - 'A'] = 2;
    code['G' - 'A'] = 3;
    code['T' - 'A'] = 4;

    vector<vector<vector<ll>>> v(5, vector<vector<ll>> (n + 1, vector<ll> (m + 1, 0)));
    for(int i = 1; i <= n; i ++) {
        string s;
        cin >> s;

        for(int j = 0; j < m; j ++)
            v[code[s[j] - 'A']][i][j + 1] = 1;
    }

    srand(time(NULL));

    vector<ll> hs(n + 1, 0);
    for(int i = 1; i <= n; i ++)
        hs[i] = rand();

    vector<ll> ans(n + 1, 0);
    for(int i = 1; i <= 4; i ++) {
        vector<vector<ll>> t(m + 1, vector<ll> (n + 1, 0));
        transpune(v[i], t, n, m);

        vector<ll> ths(m + 1, 0);
        multiply(t, hs, ths, m, n);

        vector<ll> aux(n + 1, 0);
        multiply(v[i], ths, aux, n, m);
        add(ans, aux, n);
    }

    vector<vector<ll>> sol(n + 1, vector<ll> (n + 1, k));
    for(int i = 1; i <= n; i ++)
        sol[i][i] = m;
    vector<ll> solhs(n + 1, 0);
    multiply(sol, hs, solhs, n, n);

    for(int i = 1; i <= n; i ++) {
        if(solhs[i] == ans[i]) {
            cout << i;
            return 0;
        }
    }

    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 888 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 6 ms 888 KB Output is correct
15 Correct 5 ms 784 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 380 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 125688 KB Output is correct
2 Correct 368 ms 154872 KB Output is correct
3 Correct 359 ms 148064 KB Output is correct
4 Correct 56 ms 37624 KB Output is correct
5 Correct 368 ms 154872 KB Output is correct
6 Correct 369 ms 154872 KB Output is correct
7 Correct 150 ms 66936 KB Output is correct
8 Correct 156 ms 66936 KB Output is correct
9 Correct 330 ms 142968 KB Output is correct
10 Correct 334 ms 142968 KB Output is correct
11 Correct 303 ms 125432 KB Output is correct
12 Correct 292 ms 126072 KB Output is correct
13 Correct 301 ms 125560 KB Output is correct
14 Correct 252 ms 107896 KB Output is correct
15 Correct 254 ms 109304 KB Output is correct
16 Correct 239 ms 108792 KB Output is correct
17 Correct 350 ms 148216 KB Output is correct
18 Correct 362 ms 147320 KB Output is correct
19 Correct 347 ms 148472 KB Output is correct
20 Correct 344 ms 146552 KB Output is correct
21 Correct 349 ms 148088 KB Output is correct
22 Correct 357 ms 146936 KB Output is correct
23 Correct 358 ms 147576 KB Output is correct
24 Correct 355 ms 147704 KB Output is correct
25 Correct 353 ms 146552 KB Output is correct
26 Correct 352 ms 147704 KB Output is correct
27 Correct 354 ms 146808 KB Output is correct
28 Correct 360 ms 146656 KB Output is correct
29 Correct 347 ms 147576 KB Output is correct
30 Correct 370 ms 155128 KB Output is correct
31 Correct 366 ms 154872 KB Output is correct
32 Correct 377 ms 155128 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 888 KB Output is correct
35 Correct 5 ms 376 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 125688 KB Output is correct
2 Correct 368 ms 154872 KB Output is correct
3 Correct 359 ms 148064 KB Output is correct
4 Correct 56 ms 37624 KB Output is correct
5 Correct 368 ms 154872 KB Output is correct
6 Correct 369 ms 154872 KB Output is correct
7 Correct 150 ms 66936 KB Output is correct
8 Correct 156 ms 66936 KB Output is correct
9 Correct 330 ms 142968 KB Output is correct
10 Correct 334 ms 142968 KB Output is correct
11 Correct 303 ms 125432 KB Output is correct
12 Correct 292 ms 126072 KB Output is correct
13 Correct 301 ms 125560 KB Output is correct
14 Correct 252 ms 107896 KB Output is correct
15 Correct 254 ms 109304 KB Output is correct
16 Correct 239 ms 108792 KB Output is correct
17 Correct 350 ms 148216 KB Output is correct
18 Correct 362 ms 147320 KB Output is correct
19 Correct 347 ms 148472 KB Output is correct
20 Correct 344 ms 146552 KB Output is correct
21 Correct 349 ms 148088 KB Output is correct
22 Correct 357 ms 146936 KB Output is correct
23 Correct 358 ms 147576 KB Output is correct
24 Correct 355 ms 147704 KB Output is correct
25 Correct 353 ms 146552 KB Output is correct
26 Correct 352 ms 147704 KB Output is correct
27 Correct 354 ms 146808 KB Output is correct
28 Correct 360 ms 146656 KB Output is correct
29 Correct 347 ms 147576 KB Output is correct
30 Correct 370 ms 155128 KB Output is correct
31 Correct 366 ms 154872 KB Output is correct
32 Correct 377 ms 155128 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 888 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 1853 ms 693500 KB Output is correct
37 Execution timed out 2131 ms 791932 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 888 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 6 ms 888 KB Output is correct
15 Correct 5 ms 784 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 380 KB Output is correct
18 Correct 302 ms 125688 KB Output is correct
19 Correct 368 ms 154872 KB Output is correct
20 Correct 359 ms 148064 KB Output is correct
21 Correct 56 ms 37624 KB Output is correct
22 Correct 368 ms 154872 KB Output is correct
23 Correct 369 ms 154872 KB Output is correct
24 Correct 150 ms 66936 KB Output is correct
25 Correct 156 ms 66936 KB Output is correct
26 Correct 330 ms 142968 KB Output is correct
27 Correct 334 ms 142968 KB Output is correct
28 Correct 303 ms 125432 KB Output is correct
29 Correct 292 ms 126072 KB Output is correct
30 Correct 301 ms 125560 KB Output is correct
31 Correct 252 ms 107896 KB Output is correct
32 Correct 254 ms 109304 KB Output is correct
33 Correct 239 ms 108792 KB Output is correct
34 Correct 350 ms 148216 KB Output is correct
35 Correct 362 ms 147320 KB Output is correct
36 Correct 347 ms 148472 KB Output is correct
37 Correct 344 ms 146552 KB Output is correct
38 Correct 349 ms 148088 KB Output is correct
39 Correct 357 ms 146936 KB Output is correct
40 Correct 358 ms 147576 KB Output is correct
41 Correct 355 ms 147704 KB Output is correct
42 Correct 353 ms 146552 KB Output is correct
43 Correct 352 ms 147704 KB Output is correct
44 Correct 354 ms 146808 KB Output is correct
45 Correct 360 ms 146656 KB Output is correct
46 Correct 347 ms 147576 KB Output is correct
47 Correct 370 ms 155128 KB Output is correct
48 Correct 366 ms 154872 KB Output is correct
49 Correct 377 ms 155128 KB Output is correct
50 Correct 5 ms 376 KB Output is correct
51 Correct 5 ms 888 KB Output is correct
52 Correct 5 ms 376 KB Output is correct
53 Correct 1853 ms 693500 KB Output is correct
54 Execution timed out 2131 ms 791932 KB Time limit exceeded
55 Halted 0 ms 0 KB -