# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
252786 | 2020-07-26T09:16:37 Z | evpipis | Genetics (BOI18_genetics) | C++11 | 649 ms | 82936 KB |
#include <bits/stdc++.h> using namespace std; const int len = 4105, base = 53, mod = 1e9+7; char str[len]; int arr[len][len], col[len][4], po[len]; int add(int a, int b){ return (a+b)%mod; } int mul(int a, int b){ return (a*1LL*b)%mod; } int to(char a){ if (a == 'A') return 0; if (a == 'C') return 1; if (a == 'G') return 2; return 3; } int main(){ int n, m, k; scanf("%d %d %d", &n, &m, &k); for (int i = 0; i < n; i++){ scanf("%s", &str); for (int j = 0; j < m; j++) arr[i][j] = to(str[j]); } po[0] = 1; for (int i = 1; i < n; i++) po[i] = mul(po[i-1], base); for (int j = 0; j < m; j++){ for (int i = 0; i < n; i++) col[j][arr[i][j]] = add(col[j][arr[i][j]], po[i]); } for (int i = 0; i < n; i++){ int all = 0, cur = 0; for (int j = 0; j < n; j++) if (i != j) all = add(all, mul(k, po[j])); for (int j = 0; j < m; j++) for (int l = 0; l < 4; l++) if (arr[i][j] != l) cur = add(cur, col[j][l]); //printf("i = %d, all = %d, cur = %d\n", i, all, cur); if (cur == all){ printf("%d\n", i+1); return 0; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 768 KB | Output is correct |
2 | Correct | 1 ms | 768 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 640 KB | Output is correct |
5 | Correct | 1 ms | 768 KB | Output is correct |
6 | Correct | 1 ms | 768 KB | Output is correct |
7 | Correct | 1 ms | 512 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 640 KB | Output is correct |
10 | Correct | 1 ms | 768 KB | Output is correct |
11 | Correct | 1 ms | 768 KB | Output is correct |
12 | Correct | 1 ms | 768 KB | Output is correct |
13 | Correct | 1 ms | 776 KB | Output is correct |
14 | Correct | 1 ms | 768 KB | Output is correct |
15 | Correct | 1 ms | 768 KB | Output is correct |
16 | Correct | 1 ms | 768 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 19192 KB | Output is correct |
2 | Correct | 108 ms | 23416 KB | Output is correct |
3 | Correct | 127 ms | 22472 KB | Output is correct |
4 | Correct | 37 ms | 8312 KB | Output is correct |
5 | Correct | 90 ms | 23416 KB | Output is correct |
6 | Correct | 96 ms | 23472 KB | Output is correct |
7 | Correct | 52 ms | 10232 KB | Output is correct |
8 | Correct | 44 ms | 10232 KB | Output is correct |
9 | Correct | 75 ms | 21880 KB | Output is correct |
10 | Correct | 129 ms | 21880 KB | Output is correct |
11 | Correct | 95 ms | 19320 KB | Output is correct |
12 | Correct | 61 ms | 19320 KB | Output is correct |
13 | Correct | 78 ms | 19192 KB | Output is correct |
14 | Correct | 108 ms | 16504 KB | Output is correct |
15 | Correct | 57 ms | 16632 KB | Output is correct |
16 | Correct | 65 ms | 17272 KB | Output is correct |
17 | Correct | 122 ms | 22520 KB | Output is correct |
18 | Correct | 74 ms | 22264 KB | Output is correct |
19 | Correct | 108 ms | 22580 KB | Output is correct |
20 | Correct | 84 ms | 22264 KB | Output is correct |
21 | Correct | 111 ms | 22392 KB | Output is correct |
22 | Correct | 138 ms | 22296 KB | Output is correct |
23 | Correct | 143 ms | 22412 KB | Output is correct |
24 | Correct | 134 ms | 22348 KB | Output is correct |
25 | Correct | 85 ms | 22136 KB | Output is correct |
26 | Correct | 110 ms | 22392 KB | Output is correct |
27 | Correct | 94 ms | 22392 KB | Output is correct |
28 | Correct | 95 ms | 22136 KB | Output is correct |
29 | Correct | 111 ms | 22392 KB | Output is correct |
30 | Correct | 75 ms | 23416 KB | Output is correct |
31 | Correct | 100 ms | 23416 KB | Output is correct |
32 | Correct | 94 ms | 23544 KB | Output is correct |
33 | Correct | 0 ms | 384 KB | Output is correct |
34 | Correct | 4 ms | 768 KB | Output is correct |
35 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 19192 KB | Output is correct |
2 | Correct | 108 ms | 23416 KB | Output is correct |
3 | Correct | 127 ms | 22472 KB | Output is correct |
4 | Correct | 37 ms | 8312 KB | Output is correct |
5 | Correct | 90 ms | 23416 KB | Output is correct |
6 | Correct | 96 ms | 23472 KB | Output is correct |
7 | Correct | 52 ms | 10232 KB | Output is correct |
8 | Correct | 44 ms | 10232 KB | Output is correct |
9 | Correct | 75 ms | 21880 KB | Output is correct |
10 | Correct | 129 ms | 21880 KB | Output is correct |
11 | Correct | 95 ms | 19320 KB | Output is correct |
12 | Correct | 61 ms | 19320 KB | Output is correct |
13 | Correct | 78 ms | 19192 KB | Output is correct |
14 | Correct | 108 ms | 16504 KB | Output is correct |
15 | Correct | 57 ms | 16632 KB | Output is correct |
16 | Correct | 65 ms | 17272 KB | Output is correct |
17 | Correct | 122 ms | 22520 KB | Output is correct |
18 | Correct | 74 ms | 22264 KB | Output is correct |
19 | Correct | 108 ms | 22580 KB | Output is correct |
20 | Correct | 84 ms | 22264 KB | Output is correct |
21 | Correct | 111 ms | 22392 KB | Output is correct |
22 | Correct | 138 ms | 22296 KB | Output is correct |
23 | Correct | 143 ms | 22412 KB | Output is correct |
24 | Correct | 134 ms | 22348 KB | Output is correct |
25 | Correct | 85 ms | 22136 KB | Output is correct |
26 | Correct | 110 ms | 22392 KB | Output is correct |
27 | Correct | 94 ms | 22392 KB | Output is correct |
28 | Correct | 95 ms | 22136 KB | Output is correct |
29 | Correct | 111 ms | 22392 KB | Output is correct |
30 | Correct | 75 ms | 23416 KB | Output is correct |
31 | Correct | 100 ms | 23416 KB | Output is correct |
32 | Correct | 94 ms | 23544 KB | Output is correct |
33 | Correct | 0 ms | 384 KB | Output is correct |
34 | Correct | 4 ms | 768 KB | Output is correct |
35 | Correct | 1 ms | 384 KB | Output is correct |
36 | Correct | 456 ms | 72448 KB | Output is correct |
37 | Correct | 452 ms | 82684 KB | Output is correct |
38 | Correct | 638 ms | 80888 KB | Output is correct |
39 | Correct | 209 ms | 43512 KB | Output is correct |
40 | Correct | 541 ms | 82808 KB | Output is correct |
41 | Correct | 271 ms | 41720 KB | Output is correct |
42 | Correct | 239 ms | 41464 KB | Output is correct |
43 | Correct | 324 ms | 67576 KB | Output is correct |
44 | Correct | 430 ms | 82708 KB | Output is correct |
45 | Correct | 589 ms | 82704 KB | Output is correct |
46 | Correct | 417 ms | 82808 KB | Output is correct |
47 | Correct | 489 ms | 72532 KB | Output is correct |
48 | Correct | 572 ms | 72440 KB | Output is correct |
49 | Correct | 336 ms | 62200 KB | Output is correct |
50 | Correct | 459 ms | 62200 KB | Output is correct |
51 | Correct | 481 ms | 69880 KB | Output is correct |
52 | Correct | 606 ms | 80764 KB | Output is correct |
53 | Correct | 617 ms | 80636 KB | Output is correct |
54 | Correct | 371 ms | 80504 KB | Output is correct |
55 | Correct | 548 ms | 80504 KB | Output is correct |
56 | Correct | 409 ms | 80376 KB | Output is correct |
57 | Correct | 648 ms | 81144 KB | Output is correct |
58 | Correct | 517 ms | 80888 KB | Output is correct |
59 | Correct | 448 ms | 80380 KB | Output is correct |
60 | Correct | 434 ms | 81016 KB | Output is correct |
61 | Correct | 453 ms | 80376 KB | Output is correct |
62 | Correct | 430 ms | 80120 KB | Output is correct |
63 | Correct | 399 ms | 80888 KB | Output is correct |
64 | Correct | 430 ms | 80760 KB | Output is correct |
65 | Correct | 592 ms | 80504 KB | Output is correct |
66 | Correct | 568 ms | 80760 KB | Output is correct |
67 | Correct | 569 ms | 81048 KB | Output is correct |
68 | Correct | 487 ms | 81016 KB | Output is correct |
69 | Correct | 394 ms | 80584 KB | Output is correct |
70 | Correct | 561 ms | 80760 KB | Output is correct |
71 | Correct | 475 ms | 80504 KB | Output is correct |
72 | Correct | 504 ms | 81144 KB | Output is correct |
73 | Correct | 541 ms | 80760 KB | Output is correct |
74 | Correct | 1 ms | 384 KB | Output is correct |
75 | Correct | 1 ms | 768 KB | Output is correct |
76 | Correct | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 768 KB | Output is correct |
2 | Correct | 1 ms | 768 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 640 KB | Output is correct |
5 | Correct | 1 ms | 768 KB | Output is correct |
6 | Correct | 1 ms | 768 KB | Output is correct |
7 | Correct | 1 ms | 512 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 640 KB | Output is correct |
10 | Correct | 1 ms | 768 KB | Output is correct |
11 | Correct | 1 ms | 768 KB | Output is correct |
12 | Correct | 1 ms | 768 KB | Output is correct |
13 | Correct | 1 ms | 776 KB | Output is correct |
14 | Correct | 1 ms | 768 KB | Output is correct |
15 | Correct | 1 ms | 768 KB | Output is correct |
16 | Correct | 1 ms | 768 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 104 ms | 19192 KB | Output is correct |
19 | Correct | 108 ms | 23416 KB | Output is correct |
20 | Correct | 127 ms | 22472 KB | Output is correct |
21 | Correct | 37 ms | 8312 KB | Output is correct |
22 | Correct | 90 ms | 23416 KB | Output is correct |
23 | Correct | 96 ms | 23472 KB | Output is correct |
24 | Correct | 52 ms | 10232 KB | Output is correct |
25 | Correct | 44 ms | 10232 KB | Output is correct |
26 | Correct | 75 ms | 21880 KB | Output is correct |
27 | Correct | 129 ms | 21880 KB | Output is correct |
28 | Correct | 95 ms | 19320 KB | Output is correct |
29 | Correct | 61 ms | 19320 KB | Output is correct |
30 | Correct | 78 ms | 19192 KB | Output is correct |
31 | Correct | 108 ms | 16504 KB | Output is correct |
32 | Correct | 57 ms | 16632 KB | Output is correct |
33 | Correct | 65 ms | 17272 KB | Output is correct |
34 | Correct | 122 ms | 22520 KB | Output is correct |
35 | Correct | 74 ms | 22264 KB | Output is correct |
36 | Correct | 108 ms | 22580 KB | Output is correct |
37 | Correct | 84 ms | 22264 KB | Output is correct |
38 | Correct | 111 ms | 22392 KB | Output is correct |
39 | Correct | 138 ms | 22296 KB | Output is correct |
40 | Correct | 143 ms | 22412 KB | Output is correct |
41 | Correct | 134 ms | 22348 KB | Output is correct |
42 | Correct | 85 ms | 22136 KB | Output is correct |
43 | Correct | 110 ms | 22392 KB | Output is correct |
44 | Correct | 94 ms | 22392 KB | Output is correct |
45 | Correct | 95 ms | 22136 KB | Output is correct |
46 | Correct | 111 ms | 22392 KB | Output is correct |
47 | Correct | 75 ms | 23416 KB | Output is correct |
48 | Correct | 100 ms | 23416 KB | Output is correct |
49 | Correct | 94 ms | 23544 KB | Output is correct |
50 | Correct | 0 ms | 384 KB | Output is correct |
51 | Correct | 4 ms | 768 KB | Output is correct |
52 | Correct | 1 ms | 384 KB | Output is correct |
53 | Correct | 456 ms | 72448 KB | Output is correct |
54 | Correct | 452 ms | 82684 KB | Output is correct |
55 | Correct | 638 ms | 80888 KB | Output is correct |
56 | Correct | 209 ms | 43512 KB | Output is correct |
57 | Correct | 541 ms | 82808 KB | Output is correct |
58 | Correct | 271 ms | 41720 KB | Output is correct |
59 | Correct | 239 ms | 41464 KB | Output is correct |
60 | Correct | 324 ms | 67576 KB | Output is correct |
61 | Correct | 430 ms | 82708 KB | Output is correct |
62 | Correct | 589 ms | 82704 KB | Output is correct |
63 | Correct | 417 ms | 82808 KB | Output is correct |
64 | Correct | 489 ms | 72532 KB | Output is correct |
65 | Correct | 572 ms | 72440 KB | Output is correct |
66 | Correct | 336 ms | 62200 KB | Output is correct |
67 | Correct | 459 ms | 62200 KB | Output is correct |
68 | Correct | 481 ms | 69880 KB | Output is correct |
69 | Correct | 606 ms | 80764 KB | Output is correct |
70 | Correct | 617 ms | 80636 KB | Output is correct |
71 | Correct | 371 ms | 80504 KB | Output is correct |
72 | Correct | 548 ms | 80504 KB | Output is correct |
73 | Correct | 409 ms | 80376 KB | Output is correct |
74 | Correct | 648 ms | 81144 KB | Output is correct |
75 | Correct | 517 ms | 80888 KB | Output is correct |
76 | Correct | 448 ms | 80380 KB | Output is correct |
77 | Correct | 434 ms | 81016 KB | Output is correct |
78 | Correct | 453 ms | 80376 KB | Output is correct |
79 | Correct | 430 ms | 80120 KB | Output is correct |
80 | Correct | 399 ms | 80888 KB | Output is correct |
81 | Correct | 430 ms | 80760 KB | Output is correct |
82 | Correct | 592 ms | 80504 KB | Output is correct |
83 | Correct | 568 ms | 80760 KB | Output is correct |
84 | Correct | 569 ms | 81048 KB | Output is correct |
85 | Correct | 487 ms | 81016 KB | Output is correct |
86 | Correct | 394 ms | 80584 KB | Output is correct |
87 | Correct | 561 ms | 80760 KB | Output is correct |
88 | Correct | 475 ms | 80504 KB | Output is correct |
89 | Correct | 504 ms | 81144 KB | Output is correct |
90 | Correct | 541 ms | 80760 KB | Output is correct |
91 | Correct | 1 ms | 384 KB | Output is correct |
92 | Correct | 1 ms | 768 KB | Output is correct |
93 | Correct | 0 ms | 384 KB | Output is correct |
94 | Correct | 372 ms | 78276 KB | Output is correct |
95 | Correct | 488 ms | 82680 KB | Output is correct |
96 | Correct | 649 ms | 81272 KB | Output is correct |
97 | Correct | 336 ms | 44408 KB | Output is correct |
98 | Correct | 223 ms | 43384 KB | Output is correct |
99 | Correct | 573 ms | 82808 KB | Output is correct |
100 | Correct | 267 ms | 41464 KB | Output is correct |
101 | Correct | 240 ms | 41684 KB | Output is correct |
102 | Correct | 300 ms | 67836 KB | Output is correct |
103 | Correct | 467 ms | 82808 KB | Output is correct |
104 | Correct | 597 ms | 82680 KB | Output is correct |
105 | Correct | 644 ms | 82808 KB | Output is correct |
106 | Correct | 571 ms | 78712 KB | Output is correct |
107 | Correct | 382 ms | 72476 KB | Output is correct |
108 | Correct | 412 ms | 62200 KB | Output is correct |
109 | Correct | 464 ms | 71288 KB | Output is correct |
110 | Correct | 516 ms | 69496 KB | Output is correct |
111 | Correct | 457 ms | 82808 KB | Output is correct |
112 | Correct | 554 ms | 81656 KB | Output is correct |
113 | Correct | 558 ms | 80376 KB | Output is correct |
114 | Correct | 356 ms | 80408 KB | Output is correct |
115 | Correct | 582 ms | 80376 KB | Output is correct |
116 | Correct | 610 ms | 81656 KB | Output is correct |
117 | Correct | 583 ms | 81784 KB | Output is correct |
118 | Correct | 553 ms | 81784 KB | Output is correct |
119 | Correct | 496 ms | 81528 KB | Output is correct |
120 | Correct | 595 ms | 81924 KB | Output is correct |
121 | Correct | 454 ms | 72444 KB | Output is correct |
122 | Correct | 446 ms | 82936 KB | Output is correct |
123 | Correct | 639 ms | 80888 KB | Output is correct |
124 | Correct | 0 ms | 384 KB | Output is correct |
125 | Correct | 1 ms | 768 KB | Output is correct |
126 | Correct | 0 ms | 384 KB | Output is correct |