oj.uz

Submission #984463

# Submission time Handle Problem Language Result Execution time Memory
984463 2024-05-16T17:06:39 Z Mizo_Compiler Genetics (BOI18_genetics) C++17
74 / 100
 1354 ms 91028 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("popcnt")
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
const int N = 4100;
int n, m, k, id[30], c[N][N], lim = 4;
bitset<N> b[N][4];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    id[int('A'-'A')] = 0;
    id[int('G'-'A')] = 2;
    id[int('T'-'A')] = 3;
    id[int('C'-'A')] = 1;
    if (max(n, m) > 1800) {
        lim = 2;
    }
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            b[i][id[int(s[j]-'A')]][j] = true;
        }
        for (int j = i-1; j >= 0; j--) {
            for (int kk = 0; kk < lim; kk++) {
                c[i][j] += (b[i][kk] & b[j][kk]).count();
            }
            c[j][i] = c[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        bool f = true;
        for (int j = 0; j < n && f; j++) {
            if (j == i)continue;
            f &= (c[i][j] == m-k);
        }
        if (f) {
            cout << i+1;
            return 0;
        }
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 2 ms 824 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 19676 KB Output is correct
2 Correct 463 ms 24400 KB Output is correct
3 Correct 460 ms 23204 KB Output is correct
4 Correct 195 ms 14520 KB Output is correct
5 Correct 449 ms 24400 KB Output is correct
6 Correct 477 ms 24772 KB Output is correct
7 Correct 83 ms 7284 KB Output is correct
8 Correct 83 ms 7176 KB Output is correct
9 Correct 420 ms 23444 KB Output is correct
10 Correct 415 ms 23324 KB Output is correct
11 Correct 332 ms 19632 KB Output is correct
12 Correct 344 ms 19812 KB Output is correct
13 Correct 335 ms 19968 KB Output is correct
14 Correct 235 ms 16444 KB Output is correct
15 Correct 247 ms 16744 KB Output is correct
16 Correct 309 ms 19024 KB Output is correct
17 Correct 442 ms 23368 KB Output is correct
18 Correct 429 ms 23120 KB Output is correct
19 Correct 412 ms 23196 KB Output is correct
20 Correct 418 ms 23124 KB Output is correct
21 Correct 420 ms 23124 KB Output is correct
22 Correct 423 ms 23096 KB Output is correct
23 Correct 408 ms 23116 KB Output is correct
24 Correct 429 ms 23212 KB Output is correct
25 Correct 406 ms 22864 KB Output is correct
26 Correct 413 ms 23124 KB Output is correct
27 Correct 418 ms 23044 KB Output is correct
28 Correct 402 ms 22868 KB Output is correct
29 Correct 454 ms 23036 KB Output is correct
30 Correct 458 ms 24656 KB Output is correct
31 Correct 458 ms 24528 KB Output is correct
32 Correct 476 ms 24608 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 1 ms 348 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 19676 KB Output is correct
2 Correct 463 ms 24400 KB Output is correct
3 Correct 460 ms 23204 KB Output is correct
4 Correct 195 ms 14520 KB Output is correct
5 Correct 449 ms 24400 KB Output is correct
6 Correct 477 ms 24772 KB Output is correct
7 Correct 83 ms 7284 KB Output is correct
8 Correct 83 ms 7176 KB Output is correct
9 Correct 420 ms 23444 KB Output is correct
10 Correct 415 ms 23324 KB Output is correct
11 Correct 332 ms 19632 KB Output is correct
12 Correct 344 ms 19812 KB Output is correct
13 Correct 335 ms 19968 KB Output is correct
14 Correct 235 ms 16444 KB Output is correct
15 Correct 247 ms 16744 KB Output is correct
16 Correct 309 ms 19024 KB Output is correct
17 Correct 442 ms 23368 KB Output is correct
18 Correct 429 ms 23120 KB Output is correct
19 Correct 412 ms 23196 KB Output is correct
20 Correct 418 ms 23124 KB Output is correct
21 Correct 420 ms 23124 KB Output is correct
22 Correct 423 ms 23096 KB Output is correct
23 Correct 408 ms 23116 KB Output is correct
24 Correct 429 ms 23212 KB Output is correct
25 Correct 406 ms 22864 KB Output is correct
26 Correct 413 ms 23124 KB Output is correct
27 Correct 418 ms 23044 KB Output is correct
28 Correct 402 ms 22868 KB Output is correct
29 Correct 454 ms 23036 KB Output is correct
30 Correct 458 ms 24656 KB Output is correct
31 Correct 458 ms 24528 KB Output is correct
32 Correct 476 ms 24608 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1014 ms 65388 KB Output is correct
37 Correct 1346 ms 75540 KB Output is correct
38 Correct 1312 ms 88804 KB Output is correct
39 Correct 892 ms 68784 KB Output is correct
40 Correct 1339 ms 90992 KB Output is correct
41 Correct 338 ms 37520 KB Output is correct
42 Correct 343 ms 37460 KB Output is correct
43 Correct 955 ms 74484 KB Output is correct
44 Correct 1331 ms 91028 KB Output is correct
45 Correct 1291 ms 90800 KB Output is correct
46 Correct 1315 ms 90868 KB Output is correct
47 Correct 1010 ms 79780 KB Output is correct
48 Correct 997 ms 79816 KB Output is correct
49 Correct 748 ms 68436 KB Output is correct
50 Correct 783 ms 68696 KB Output is correct
51 Correct 975 ms 76864 KB Output is correct
52 Correct 1331 ms 88888 KB Output is correct
53 Correct 1262 ms 88500 KB Output is correct
54 Correct 1324 ms 88508 KB Output is correct
55 Correct 1259 ms 88356 KB Output is correct
56 Correct 1335 ms 88420 KB Output is correct
57 Correct 1300 ms 88924 KB Output is correct
58 Correct 1306 ms 89316 KB Output is correct
59 Correct 1319 ms 88280 KB Output is correct
60 Correct 1286 ms 89100 KB Output is correct
61 Correct 1261 ms 88544 KB Output is correct
62 Correct 1314 ms 88192 KB Output is correct
63 Correct 1264 ms 88888 KB Output is correct
64 Correct 1271 ms 88836 KB Output is correct
65 Correct 1275 ms 88528 KB Output is correct
66 Correct 1343 ms 88820 KB Output is correct
67 Correct 1296 ms 88972 KB Output is correct
68 Correct 1312 ms 89168 KB Output is correct
69 Correct 1354 ms 88540 KB Output is correct
70 Correct 1338 ms 89400 KB Output is correct
71 Correct 1339 ms 88380 KB Output is correct
72 Correct 1351 ms 89552 KB Output is correct
73 Correct 1297 ms 88652 KB Output is correct
74 Correct 0 ms 348 KB Output is correct
75 Correct 2 ms 928 KB Output is correct
76 Correct 0 ms 468 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 2 ms 824 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 339 ms 19676 KB Output is correct
19 Correct 463 ms 24400 KB Output is correct
20 Correct 460 ms 23204 KB Output is correct
21 Correct 195 ms 14520 KB Output is correct
22 Correct 449 ms 24400 KB Output is correct
23 Correct 477 ms 24772 KB Output is correct
24 Correct 83 ms 7284 KB Output is correct
25 Correct 83 ms 7176 KB Output is correct
26 Correct 420 ms 23444 KB Output is correct
27 Correct 415 ms 23324 KB Output is correct
28 Correct 332 ms 19632 KB Output is correct
29 Correct 344 ms 19812 KB Output is correct
30 Correct 335 ms 19968 KB Output is correct
31 Correct 235 ms 16444 KB Output is correct
32 Correct 247 ms 16744 KB Output is correct
33 Correct 309 ms 19024 KB Output is correct
34 Correct 442 ms 23368 KB Output is correct
35 Correct 429 ms 23120 KB Output is correct
36 Correct 412 ms 23196 KB Output is correct
37 Correct 418 ms 23124 KB Output is correct
38 Correct 420 ms 23124 KB Output is correct
39 Correct 423 ms 23096 KB Output is correct
40 Correct 408 ms 23116 KB Output is correct
41 Correct 429 ms 23212 KB Output is correct
42 Correct 406 ms 22864 KB Output is correct
43 Correct 413 ms 23124 KB Output is correct
44 Correct 418 ms 23044 KB Output is correct
45 Correct 402 ms 22868 KB Output is correct
46 Correct 454 ms 23036 KB Output is correct
47 Correct 458 ms 24656 KB Output is correct
48 Correct 458 ms 24528 KB Output is correct
49 Correct 476 ms 24608 KB Output is correct
50 Correct 0 ms 344 KB Output is correct
51 Correct 2 ms 856 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1014 ms 65388 KB Output is correct
54 Correct 1346 ms 75540 KB Output is correct
55 Correct 1312 ms 88804 KB Output is correct
56 Correct 892 ms 68784 KB Output is correct
57 Correct 1339 ms 90992 KB Output is correct
58 Correct 338 ms 37520 KB Output is correct
59 Correct 343 ms 37460 KB Output is correct
60 Correct 955 ms 74484 KB Output is correct
61 Correct 1331 ms 91028 KB Output is correct
62 Correct 1291 ms 90800 KB Output is correct
63 Correct 1315 ms 90868 KB Output is correct
64 Correct 1010 ms 79780 KB Output is correct
65 Correct 997 ms 79816 KB Output is correct
66 Correct 748 ms 68436 KB Output is correct
67 Correct 783 ms 68696 KB Output is correct
68 Correct 975 ms 76864 KB Output is correct
69 Correct 1331 ms 88888 KB Output is correct
70 Correct 1262 ms 88500 KB Output is correct
71 Correct 1324 ms 88508 KB Output is correct
72 Correct 1259 ms 88356 KB Output is correct
73 Correct 1335 ms 88420 KB Output is correct
74 Correct 1300 ms 88924 KB Output is correct
75 Correct 1306 ms 89316 KB Output is correct
76 Correct 1319 ms 88280 KB Output is correct
77 Correct 1286 ms 89100 KB Output is correct
78 Correct 1261 ms 88544 KB Output is correct
79 Correct 1314 ms 88192 KB Output is correct
80 Correct 1264 ms 88888 KB Output is correct
81 Correct 1271 ms 88836 KB Output is correct
82 Correct 1275 ms 88528 KB Output is correct
83 Correct 1343 ms 88820 KB Output is correct
84 Correct 1296 ms 88972 KB Output is correct
85 Correct 1312 ms 89168 KB Output is correct
86 Correct 1354 ms 88540 KB Output is correct
87 Correct 1338 ms 89400 KB Output is correct
88 Correct 1339 ms 88380 KB Output is correct
89 Correct 1351 ms 89552 KB Output is correct
90 Correct 1297 ms 88652 KB Output is correct
91 Correct 0 ms 348 KB Output is correct
92 Correct 2 ms 928 KB Output is correct
93 Correct 0 ms 468 KB Output is correct
94 Incorrect 1251 ms 86432 KB Output isn't correct
95 Halted 0 ms 0 KB -