oj.uz

Submission #524665

# Submission time Handle Problem Language Result Execution time Memory
524665 2022-02-09T18:31:25 Z Yazan_Alattar Genetics (BOI18_genetics) C++14
100 / 100
 671 ms 164932 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 5007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int to(char x)
{
	if(x == 'A') return 0;
	if(x == 'C') return 1;
	if(x == 'G') return 2;
	return 3;
}

ll n, m, k, a[M][M], cnt[M][4], w[M], tot;

int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i){
		string s; cin >> s;
		w[i] = rand();
		tot += w[i];
		for(int j = 1; j <= m; ++j){
			a[i][j] = to(s[j - 1]);
			cnt[j][a[i][j]] += w[i];
		}
	}
	for(int i = 1; i <= n; ++i){
		ll sum = 0;
		for(int j = 1; j <= m; ++j)	sum += tot - cnt[j][a[i][j]];
		if(sum == (tot - w[i]) * k) cout << i << endl, exit(0);
	}
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 688 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 812 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 688 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 688 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 332 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 29376 KB Output is correct
2 Correct 94 ms 36036 KB Output is correct
3 Correct 103 ms 34400 KB Output is correct
4 Correct 23 ms 10828 KB Output is correct
5 Correct 94 ms 36068 KB Output is correct
6 Correct 99 ms 36128 KB Output is correct
7 Correct 47 ms 15532 KB Output is correct
8 Correct 41 ms 15512 KB Output is correct
9 Correct 95 ms 33560 KB Output is correct
10 Correct 101 ms 33556 KB Output is correct
11 Correct 80 ms 29360 KB Output is correct
12 Correct 77 ms 29608 KB Output is correct
13 Correct 79 ms 29368 KB Output is correct
14 Correct 70 ms 25228 KB Output is correct
15 Correct 69 ms 25516 KB Output is correct
16 Correct 67 ms 26172 KB Output is correct
17 Correct 94 ms 34500 KB Output is correct
18 Correct 92 ms 34296 KB Output is correct
19 Correct 92 ms 34608 KB Output is correct
20 Correct 89 ms 34072 KB Output is correct
21 Correct 96 ms 34644 KB Output is correct
22 Correct 90 ms 34176 KB Output is correct
23 Correct 90 ms 34404 KB Output is correct
24 Correct 90 ms 34400 KB Output is correct
25 Correct 88 ms 34124 KB Output is correct
26 Correct 90 ms 34372 KB Output is correct
27 Correct 89 ms 34152 KB Output is correct
28 Correct 91 ms 34240 KB Output is correct
29 Correct 90 ms 34404 KB Output is correct
30 Correct 86 ms 36084 KB Output is correct
31 Correct 88 ms 36040 KB Output is correct
32 Correct 105 ms 36236 KB Output is correct
33 Correct 0 ms 300 KB Output is correct
34 Correct 1 ms 716 KB Output is correct
35 Correct 0 ms 332 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 29376 KB Output is correct
2 Correct 94 ms 36036 KB Output is correct
3 Correct 103 ms 34400 KB Output is correct
4 Correct 23 ms 10828 KB Output is correct
5 Correct 94 ms 36068 KB Output is correct
6 Correct 99 ms 36128 KB Output is correct
7 Correct 47 ms 15532 KB Output is correct
8 Correct 41 ms 15512 KB Output is correct
9 Correct 95 ms 33560 KB Output is correct
10 Correct 101 ms 33556 KB Output is correct
11 Correct 80 ms 29360 KB Output is correct
12 Correct 77 ms 29608 KB Output is correct
13 Correct 79 ms 29368 KB Output is correct
14 Correct 70 ms 25228 KB Output is correct
15 Correct 69 ms 25516 KB Output is correct
16 Correct 67 ms 26172 KB Output is correct
17 Correct 94 ms 34500 KB Output is correct
18 Correct 92 ms 34296 KB Output is correct
19 Correct 92 ms 34608 KB Output is correct
20 Correct 89 ms 34072 KB Output is correct
21 Correct 96 ms 34644 KB Output is correct
22 Correct 90 ms 34176 KB Output is correct
23 Correct 90 ms 34404 KB Output is correct
24 Correct 90 ms 34400 KB Output is correct
25 Correct 88 ms 34124 KB Output is correct
26 Correct 90 ms 34372 KB Output is correct
27 Correct 89 ms 34152 KB Output is correct
28 Correct 91 ms 34240 KB Output is correct
29 Correct 90 ms 34404 KB Output is correct
30 Correct 86 ms 36084 KB Output is correct
31 Correct 88 ms 36040 KB Output is correct
32 Correct 105 ms 36236 KB Output is correct
33 Correct 0 ms 300 KB Output is correct
34 Correct 1 ms 716 KB Output is correct
35 Correct 0 ms 332 KB Output is correct
36 Correct 420 ms 144048 KB Output is correct
37 Correct 437 ms 164932 KB Output is correct
38 Correct 485 ms 160812 KB Output is correct
39 Correct 175 ms 66892 KB Output is correct
40 Correct 553 ms 164604 KB Output is correct
41 Correct 242 ms 82500 KB Output is correct
42 Correct 234 ms 82520 KB Output is correct
43 Correct 337 ms 119432 KB Output is correct
44 Correct 471 ms 164732 KB Output is correct
45 Correct 479 ms 164564 KB Output is correct
46 Correct 464 ms 164640 KB Output is correct
47 Correct 413 ms 144196 KB Output is correct
48 Correct 421 ms 144104 KB Output is correct
49 Correct 352 ms 123528 KB Output is correct
50 Correct 358 ms 123572 KB Output is correct
51 Correct 403 ms 139180 KB Output is correct
52 Correct 463 ms 160508 KB Output is correct
53 Correct 468 ms 160496 KB Output is correct
54 Correct 438 ms 157324 KB Output is correct
55 Correct 426 ms 157296 KB Output is correct
56 Correct 446 ms 157308 KB Output is correct
57 Correct 469 ms 161044 KB Output is correct
58 Correct 548 ms 161164 KB Output is correct
59 Correct 462 ms 160172 KB Output is correct
60 Correct 461 ms 161124 KB Output is correct
61 Correct 463 ms 160236 KB Output is correct
62 Correct 463 ms 159504 KB Output is correct
63 Correct 468 ms 160960 KB Output is correct
64 Correct 461 ms 160836 KB Output is correct
65 Correct 471 ms 160340 KB Output is correct
66 Correct 471 ms 160596 KB Output is correct
67 Correct 472 ms 161132 KB Output is correct
68 Correct 469 ms 160948 KB Output is correct
69 Correct 458 ms 160324 KB Output is correct
70 Correct 464 ms 160864 KB Output is correct
71 Correct 465 ms 160200 KB Output is correct
72 Correct 671 ms 161412 KB Output is correct
73 Correct 485 ms 160364 KB Output is correct
74 Correct 1 ms 332 KB Output is correct
75 Correct 1 ms 692 KB Output is correct
76 Correct 0 ms 332 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 688 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 812 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 688 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 688 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 87 ms 29376 KB Output is correct
19 Correct 94 ms 36036 KB Output is correct
20 Correct 103 ms 34400 KB Output is correct
21 Correct 23 ms 10828 KB Output is correct
22 Correct 94 ms 36068 KB Output is correct
23 Correct 99 ms 36128 KB Output is correct
24 Correct 47 ms 15532 KB Output is correct
25 Correct 41 ms 15512 KB Output is correct
26 Correct 95 ms 33560 KB Output is correct
27 Correct 101 ms 33556 KB Output is correct
28 Correct 80 ms 29360 KB Output is correct
29 Correct 77 ms 29608 KB Output is correct
30 Correct 79 ms 29368 KB Output is correct
31 Correct 70 ms 25228 KB Output is correct
32 Correct 69 ms 25516 KB Output is correct
33 Correct 67 ms 26172 KB Output is correct
34 Correct 94 ms 34500 KB Output is correct
35 Correct 92 ms 34296 KB Output is correct
36 Correct 92 ms 34608 KB Output is correct
37 Correct 89 ms 34072 KB Output is correct
38 Correct 96 ms 34644 KB Output is correct
39 Correct 90 ms 34176 KB Output is correct
40 Correct 90 ms 34404 KB Output is correct
41 Correct 90 ms 34400 KB Output is correct
42 Correct 88 ms 34124 KB Output is correct
43 Correct 90 ms 34372 KB Output is correct
44 Correct 89 ms 34152 KB Output is correct
45 Correct 91 ms 34240 KB Output is correct
46 Correct 90 ms 34404 KB Output is correct
47 Correct 86 ms 36084 KB Output is correct
48 Correct 88 ms 36040 KB Output is correct
49 Correct 105 ms 36236 KB Output is correct
50 Correct 0 ms 300 KB Output is correct
51 Correct 1 ms 716 KB Output is correct
52 Correct 0 ms 332 KB Output is correct
53 Correct 420 ms 144048 KB Output is correct
54 Correct 437 ms 164932 KB Output is correct
55 Correct 485 ms 160812 KB Output is correct
56 Correct 175 ms 66892 KB Output is correct
57 Correct 553 ms 164604 KB Output is correct
58 Correct 242 ms 82500 KB Output is correct
59 Correct 234 ms 82520 KB Output is correct
60 Correct 337 ms 119432 KB Output is correct
61 Correct 471 ms 164732 KB Output is correct
62 Correct 479 ms 164564 KB Output is correct
63 Correct 464 ms 164640 KB Output is correct
64 Correct 413 ms 144196 KB Output is correct
65 Correct 421 ms 144104 KB Output is correct
66 Correct 352 ms 123528 KB Output is correct
67 Correct 358 ms 123572 KB Output is correct
68 Correct 403 ms 139180 KB Output is correct
69 Correct 463 ms 160508 KB Output is correct
70 Correct 468 ms 160496 KB Output is correct
71 Correct 438 ms 157324 KB Output is correct
72 Correct 426 ms 157296 KB Output is correct
73 Correct 446 ms 157308 KB Output is correct
74 Correct 469 ms 161044 KB Output is correct
75 Correct 548 ms 161164 KB Output is correct
76 Correct 462 ms 160172 KB Output is correct
77 Correct 461 ms 161124 KB Output is correct
78 Correct 463 ms 160236 KB Output is correct
79 Correct 463 ms 159504 KB Output is correct
80 Correct 468 ms 160960 KB Output is correct
81 Correct 461 ms 160836 KB Output is correct
82 Correct 471 ms 160340 KB Output is correct
83 Correct 471 ms 160596 KB Output is correct
84 Correct 472 ms 161132 KB Output is correct
85 Correct 469 ms 160948 KB Output is correct
86 Correct 458 ms 160324 KB Output is correct
87 Correct 464 ms 160864 KB Output is correct
88 Correct 465 ms 160200 KB Output is correct
89 Correct 671 ms 161412 KB Output is correct
90 Correct 485 ms 160364 KB Output is correct
91 Correct 1 ms 332 KB Output is correct
92 Correct 1 ms 692 KB Output is correct
93 Correct 0 ms 332 KB Output is correct
94 Correct 479 ms 155828 KB Output is correct
95 Correct 456 ms 164828 KB Output is correct
96 Correct 495 ms 161800 KB Output is correct
97 Correct 267 ms 88116 KB Output is correct
98 Correct 184 ms 66864 KB Output is correct
99 Correct 487 ms 164720 KB Output is correct
100 Correct 263 ms 82604 KB Output is correct
101 Correct 254 ms 82500 KB Output is correct
102 Correct 350 ms 119528 KB Output is correct
103 Correct 482 ms 164664 KB Output is correct
104 Correct 506 ms 164528 KB Output is correct
105 Correct 511 ms 164628 KB Output is correct
106 Correct 469 ms 156360 KB Output is correct
107 Correct 408 ms 144168 KB Output is correct
108 Correct 360 ms 123528 KB Output is correct
109 Correct 433 ms 141908 KB Output is correct
110 Correct 424 ms 136088 KB Output is correct
111 Correct 516 ms 164600 KB Output is correct
112 Correct 498 ms 162576 KB Output is correct
113 Correct 436 ms 157300 KB Output is correct
114 Correct 439 ms 157332 KB Output is correct
115 Correct 474 ms 157480 KB Output is correct
116 Correct 494 ms 162448 KB Output is correct
117 Correct 495 ms 162708 KB Output is correct
118 Correct 487 ms 162584 KB Output is correct
119 Correct 490 ms 162016 KB Output is correct
120 Correct 494 ms 162632 KB Output is correct
121 Correct 413 ms 144092 KB Output is correct
122 Correct 450 ms 164840 KB Output is correct
123 Correct 468 ms 160784 KB Output is correct
124 Correct 1 ms 296 KB Output is correct
125 Correct 1 ms 716 KB Output is correct
126 Correct 0 ms 332 KB Output is correct