oj.uz

Submission #96032

# Submission time Handle Problem Language Result Execution time Memory
96032 2019-02-05T10:15:03 Z caesar2001 Genetics (BOI18_genetics) C++14
46 / 100
 2000 ms 924744 KB 
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

const int NMAX = 4103;
char s[5 + NMAX];

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 ++)
        ans[i] = 0;
    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;
    scanf("%d%d%d\n", &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 ++) {
        fgets(s, NMAX, stdin);

        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);
    vector<vector<ll>> t(m + 1, vector<ll> (n + 1, 0));
    vector<ll> ths(m + 1, 0);
    vector<ll> aux(n + 1, 0);
    for(int i = 1; i <= 4; i ++) {
        transpune(v[i], t, n, m);

        multiply(t, hs, ths, m, n);

        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]) {
            printf("%d", i);
            return 0;
        }
    }

    return 0;
}

Compilation message

genetics.cpp: In function 'int main()':
genetics.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d\n", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:48:14: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fgets(s, NMAX, stdin);
         ~~~~~^~~~~~~~~~~~~~~~

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 636 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 888 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 632 KB Output is correct
10 Correct 5 ms 888 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 5 ms 892 KB Output is correct
15 Correct 6 ms 888 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 141688 KB Output is correct
2 Correct 358 ms 178424 KB Output is correct
3 Correct 350 ms 171984 KB Output is correct
4 Correct 57 ms 43000 KB Output is correct
5 Correct 358 ms 181240 KB Output is correct
6 Correct 360 ms 181240 KB Output is correct
7 Correct 146 ms 71540 KB Output is correct
8 Correct 145 ms 71544 KB Output is correct
9 Correct 334 ms 167160 KB Output is correct
10 Correct 328 ms 167164 KB Output is correct
11 Correct 293 ms 143864 KB Output is correct
12 Correct 284 ms 144736 KB Output is correct
13 Correct 292 ms 143752 KB Output is correct
14 Correct 265 ms 121140 KB Output is correct
15 Correct 248 ms 122744 KB Output is correct
16 Correct 236 ms 125816 KB Output is correct
17 Correct 346 ms 172468 KB Output is correct
18 Correct 347 ms 171000 KB Output is correct
19 Correct 345 ms 172664 KB Output is correct
20 Correct 331 ms 169976 KB Output is correct
21 Correct 344 ms 172152 KB Output is correct
22 Correct 343 ms 170616 KB Output is correct
23 Correct 348 ms 171512 KB Output is correct
24 Correct 342 ms 171384 KB Output is correct
25 Correct 352 ms 170104 KB Output is correct
26 Correct 345 ms 171640 KB Output is correct
27 Correct 347 ms 170360 KB Output is correct
28 Correct 345 ms 170360 KB Output is correct
29 Correct 346 ms 171512 KB Output is correct
30 Correct 361 ms 181468 KB Output is correct
31 Correct 357 ms 181240 KB Output is correct
32 Correct 363 ms 181268 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 1016 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 290 ms 141688 KB Output is correct
2 Correct 358 ms 178424 KB Output is correct
3 Correct 350 ms 171984 KB Output is correct
4 Correct 57 ms 43000 KB Output is correct
5 Correct 358 ms 181240 KB Output is correct
6 Correct 360 ms 181240 KB Output is correct
7 Correct 146 ms 71540 KB Output is correct
8 Correct 145 ms 71544 KB Output is correct
9 Correct 334 ms 167160 KB Output is correct
10 Correct 328 ms 167164 KB Output is correct
11 Correct 293 ms 143864 KB Output is correct
12 Correct 284 ms 144736 KB Output is correct
13 Correct 292 ms 143752 KB Output is correct
14 Correct 265 ms 121140 KB Output is correct
15 Correct 248 ms 122744 KB Output is correct
16 Correct 236 ms 125816 KB Output is correct
17 Correct 346 ms 172468 KB Output is correct
18 Correct 347 ms 171000 KB Output is correct
19 Correct 345 ms 172664 KB Output is correct
20 Correct 331 ms 169976 KB Output is correct
21 Correct 344 ms 172152 KB Output is correct
22 Correct 343 ms 170616 KB Output is correct
23 Correct 348 ms 171512 KB Output is correct
24 Correct 342 ms 171384 KB Output is correct
25 Correct 352 ms 170104 KB Output is correct
26 Correct 345 ms 171640 KB Output is correct
27 Correct 347 ms 170360 KB Output is correct
28 Correct 345 ms 170360 KB Output is correct
29 Correct 346 ms 171512 KB Output is correct
30 Correct 361 ms 181468 KB Output is correct
31 Correct 357 ms 181240 KB Output is correct
32 Correct 363 ms 181268 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 1016 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 1805 ms 796004 KB Output is correct
37 Execution timed out 2113 ms 924744 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 636 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 888 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 632 KB Output is correct
10 Correct 5 ms 888 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 5 ms 892 KB Output is correct
15 Correct 6 ms 888 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 290 ms 141688 KB Output is correct
19 Correct 358 ms 178424 KB Output is correct
20 Correct 350 ms 171984 KB Output is correct
21 Correct 57 ms 43000 KB Output is correct
22 Correct 358 ms 181240 KB Output is correct
23 Correct 360 ms 181240 KB Output is correct
24 Correct 146 ms 71540 KB Output is correct
25 Correct 145 ms 71544 KB Output is correct
26 Correct 334 ms 167160 KB Output is correct
27 Correct 328 ms 167164 KB Output is correct
28 Correct 293 ms 143864 KB Output is correct
29 Correct 284 ms 144736 KB Output is correct
30 Correct 292 ms 143752 KB Output is correct
31 Correct 265 ms 121140 KB Output is correct
32 Correct 248 ms 122744 KB Output is correct
33 Correct 236 ms 125816 KB Output is correct
34 Correct 346 ms 172468 KB Output is correct
35 Correct 347 ms 171000 KB Output is correct
36 Correct 345 ms 172664 KB Output is correct
37 Correct 331 ms 169976 KB Output is correct
38 Correct 344 ms 172152 KB Output is correct
39 Correct 343 ms 170616 KB Output is correct
40 Correct 348 ms 171512 KB Output is correct
41 Correct 342 ms 171384 KB Output is correct
42 Correct 352 ms 170104 KB Output is correct
43 Correct 345 ms 171640 KB Output is correct
44 Correct 347 ms 170360 KB Output is correct
45 Correct 345 ms 170360 KB Output is correct
46 Correct 346 ms 171512 KB Output is correct
47 Correct 361 ms 181468 KB Output is correct
48 Correct 357 ms 181240 KB Output is correct
49 Correct 363 ms 181268 KB Output is correct
50 Correct 5 ms 376 KB Output is correct
51 Correct 5 ms 1016 KB Output is correct
52 Correct 5 ms 376 KB Output is correct
53 Correct 1805 ms 796004 KB Output is correct
54 Execution timed out 2113 ms 924744 KB Time limit exceeded
55 Halted 0 ms 0 KB -