답안 #96036 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96036	2019-02-05T10:26:49 Z	caesar2001	Genetics (BOI18_genetics)	C++14	46 / 100	1954 ms	794488 KB

genetics

#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);
    vector<ll> ths(m + 1, 0);
    for(int color = 1; color <= 4; color ++) {
        for(int i = 1; i <= m; i ++)
            ths[i] = 0;
        for(int i = 1; i <= m; i ++)
            for(int k = 1; k <= n; k ++)
                ths[i] += (v[color][k][i] * hs[k]);

        for(int i = 1; i <= n; i ++)
            for(int k = 1; k <= m; k ++)
                ans[i] += (v[color][i][k] * ths[k]);
    }

    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

#	결과	실행 시간	메모리	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	664 KB	Output is correct
6	Correct	5 ms	760 KB	Output is correct
7	Correct	5 ms	504 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	760 KB	Output is correct
11	Correct	5 ms	760 KB	Output is correct
12	Correct	5 ms	760 KB	Output is correct
13	Correct	5 ms	888 KB	Output is correct
14	Correct	5 ms	888 KB	Output is correct
15	Correct	5 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

#	결과	실행 시간	메모리	Grader output
1	Correct	258 ms	124924 KB	Output is correct
2	Correct	349 ms	154360 KB	Output is correct
3	Correct	315 ms	147576 KB	Output is correct
4	Correct	52 ms	37624 KB	Output is correct
5	Correct	339 ms	154744 KB	Output is correct
6	Correct	366 ms	154488 KB	Output is correct
7	Correct	87 ms	66680 KB	Output is correct
8	Correct	82 ms	66680 KB	Output is correct
9	Correct	302 ms	142676 KB	Output is correct
10	Correct	337 ms	142660 KB	Output is correct
11	Correct	266 ms	125176 KB	Output is correct
12	Correct	258 ms	125816 KB	Output is correct
13	Correct	258 ms	125176 KB	Output is correct
14	Correct	204 ms	107516 KB	Output is correct
15	Correct	210 ms	108792 KB	Output is correct
16	Correct	219 ms	108408 KB	Output is correct
17	Correct	321 ms	147960 KB	Output is correct
18	Correct	328 ms	146936 KB	Output is correct
19	Correct	322 ms	148152 KB	Output is correct
20	Correct	321 ms	146168 KB	Output is correct
21	Correct	316 ms	147704 KB	Output is correct
22	Correct	321 ms	146680 KB	Output is correct
23	Correct	312 ms	147320 KB	Output is correct
24	Correct	323 ms	147272 KB	Output is correct
25	Correct	320 ms	146424 KB	Output is correct
26	Correct	326 ms	147320 KB	Output is correct
27	Correct	316 ms	146552 KB	Output is correct
28	Correct	316 ms	146296 KB	Output is correct
29	Correct	319 ms	147448 KB	Output is correct
30	Correct	336 ms	154616 KB	Output is correct
31	Correct	341 ms	154616 KB	Output is correct
32	Correct	342 ms	154528 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

#	결과	실행 시간	메모리	Grader output
1	Correct	258 ms	124924 KB	Output is correct
2	Correct	349 ms	154360 KB	Output is correct
3	Correct	315 ms	147576 KB	Output is correct
4	Correct	52 ms	37624 KB	Output is correct
5	Correct	339 ms	154744 KB	Output is correct
6	Correct	366 ms	154488 KB	Output is correct
7	Correct	87 ms	66680 KB	Output is correct
8	Correct	82 ms	66680 KB	Output is correct
9	Correct	302 ms	142676 KB	Output is correct
10	Correct	337 ms	142660 KB	Output is correct
11	Correct	266 ms	125176 KB	Output is correct
12	Correct	258 ms	125816 KB	Output is correct
13	Correct	258 ms	125176 KB	Output is correct
14	Correct	204 ms	107516 KB	Output is correct
15	Correct	210 ms	108792 KB	Output is correct
16	Correct	219 ms	108408 KB	Output is correct
17	Correct	321 ms	147960 KB	Output is correct
18	Correct	328 ms	146936 KB	Output is correct
19	Correct	322 ms	148152 KB	Output is correct
20	Correct	321 ms	146168 KB	Output is correct
21	Correct	316 ms	147704 KB	Output is correct
22	Correct	321 ms	146680 KB	Output is correct
23	Correct	312 ms	147320 KB	Output is correct
24	Correct	323 ms	147272 KB	Output is correct
25	Correct	320 ms	146424 KB	Output is correct
26	Correct	326 ms	147320 KB	Output is correct
27	Correct	316 ms	146552 KB	Output is correct
28	Correct	316 ms	146296 KB	Output is correct
29	Correct	319 ms	147448 KB	Output is correct
30	Correct	336 ms	154616 KB	Output is correct
31	Correct	341 ms	154616 KB	Output is correct
32	Correct	342 ms	154528 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	1704 ms	694216 KB	Output is correct
37	Correct	1954 ms	792440 KB	Output is correct
38	Correct	1900 ms	775688 KB	Output is correct
39	Correct	682 ms	333404 KB	Output is correct
40	Correct	1948 ms	794488 KB	Output is correct
41	Correct	929 ms	400248 KB	Output is correct
42	Correct	929 ms	400376 KB	Output is correct
43	Correct	1381 ms	567164 KB	Output is correct
44	Correct	1930 ms	794104 KB	Output is correct
45	Correct	1931 ms	794108 KB	Output is correct
46	Correct	1941 ms	794104 KB	Output is correct
47	Correct	1703 ms	697464 KB	Output is correct
48	Correct	1712 ms	705528 KB	Output is correct
49	Correct	1466 ms	604920 KB	Output is correct
50	Correct	1466 ms	604792 KB	Output is correct
51	Correct	1657 ms	681020 KB	Output is correct
52	Correct	1896 ms	785868 KB	Output is correct
53	Correct	1919 ms	785716 KB	Output is correct
54	Correct	1863 ms	768760 KB	Output is correct
55	Correct	1870 ms	768876 KB	Output is correct
56	Correct	1873 ms	768616 KB	Output is correct
57	Correct	1949 ms	788568 KB	Output is correct
58	Correct	1921 ms	788592 KB	Output is correct
59	Correct	1940 ms	784256 KB	Output is correct
60	Correct	1954 ms	789240 KB	Output is correct
61	Correct	1912 ms	784376 KB	Output is correct
62	Execution timed out	567 ms	772216 KB	Time limit exceeded (wall clock)
63	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	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	664 KB	Output is correct
6	Correct	5 ms	760 KB	Output is correct
7	Correct	5 ms	504 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	760 KB	Output is correct
11	Correct	5 ms	760 KB	Output is correct
12	Correct	5 ms	760 KB	Output is correct
13	Correct	5 ms	888 KB	Output is correct
14	Correct	5 ms	888 KB	Output is correct
15	Correct	5 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	258 ms	124924 KB	Output is correct
19	Correct	349 ms	154360 KB	Output is correct
20	Correct	315 ms	147576 KB	Output is correct
21	Correct	52 ms	37624 KB	Output is correct
22	Correct	339 ms	154744 KB	Output is correct
23	Correct	366 ms	154488 KB	Output is correct
24	Correct	87 ms	66680 KB	Output is correct
25	Correct	82 ms	66680 KB	Output is correct
26	Correct	302 ms	142676 KB	Output is correct
27	Correct	337 ms	142660 KB	Output is correct
28	Correct	266 ms	125176 KB	Output is correct
29	Correct	258 ms	125816 KB	Output is correct
30	Correct	258 ms	125176 KB	Output is correct
31	Correct	204 ms	107516 KB	Output is correct
32	Correct	210 ms	108792 KB	Output is correct
33	Correct	219 ms	108408 KB	Output is correct
34	Correct	321 ms	147960 KB	Output is correct
35	Correct	328 ms	146936 KB	Output is correct
36	Correct	322 ms	148152 KB	Output is correct
37	Correct	321 ms	146168 KB	Output is correct
38	Correct	316 ms	147704 KB	Output is correct
39	Correct	321 ms	146680 KB	Output is correct
40	Correct	312 ms	147320 KB	Output is correct
41	Correct	323 ms	147272 KB	Output is correct
42	Correct	320 ms	146424 KB	Output is correct
43	Correct	326 ms	147320 KB	Output is correct
44	Correct	316 ms	146552 KB	Output is correct
45	Correct	316 ms	146296 KB	Output is correct
46	Correct	319 ms	147448 KB	Output is correct
47	Correct	336 ms	154616 KB	Output is correct
48	Correct	341 ms	154616 KB	Output is correct
49	Correct	342 ms	154528 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	1704 ms	694216 KB	Output is correct
54	Correct	1954 ms	792440 KB	Output is correct
55	Correct	1900 ms	775688 KB	Output is correct
56	Correct	682 ms	333404 KB	Output is correct
57	Correct	1948 ms	794488 KB	Output is correct
58	Correct	929 ms	400248 KB	Output is correct
59	Correct	929 ms	400376 KB	Output is correct
60	Correct	1381 ms	567164 KB	Output is correct
61	Correct	1930 ms	794104 KB	Output is correct
62	Correct	1931 ms	794108 KB	Output is correct
63	Correct	1941 ms	794104 KB	Output is correct
64	Correct	1703 ms	697464 KB	Output is correct
65	Correct	1712 ms	705528 KB	Output is correct
66	Correct	1466 ms	604920 KB	Output is correct
67	Correct	1466 ms	604792 KB	Output is correct
68	Correct	1657 ms	681020 KB	Output is correct
69	Correct	1896 ms	785868 KB	Output is correct
70	Correct	1919 ms	785716 KB	Output is correct
71	Correct	1863 ms	768760 KB	Output is correct
72	Correct	1870 ms	768876 KB	Output is correct
73	Correct	1873 ms	768616 KB	Output is correct
74	Correct	1949 ms	788568 KB	Output is correct
75	Correct	1921 ms	788592 KB	Output is correct
76	Correct	1940 ms	784256 KB	Output is correct
77	Correct	1954 ms	789240 KB	Output is correct
78	Correct	1912 ms	784376 KB	Output is correct
79	Execution timed out	567 ms	772216 KB	Time limit exceeded (wall clock)
80	Halted	0 ms	0 KB	-

답안 #96036

Compilation message

Subtask #1 27.0 / 27.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 28.0

Subtask #4 0 / 26.0

Subtask #1
27.0 / 27.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 28.0

Subtask #4
0 / 26.0