oj.uz

Submission #488106

# Submission time Handle Problem Language Result Execution time Memory
488106 2021-11-17T17:38:45 Z MohamedAhmed04 Genetics (BOI18_genetics) C++14
100 / 100
 611 ms 36296 KB 
#include <bits/stdc++.h>

using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;

int rand(int l , int r)
{
	return uniform_int_distribution<int>(l , r)(rng) ;
}

const int MAX = 4100 + 10 ;

string arr[MAX] ;
int n , m , k ;

long long freq[MAX][4] ;
long long val[MAX] ;

int f(char c)
{
	if(c == 'A')
		return 0 ;
	else if(c == 'C')
		return 1 ;
	else if(c == 'G')
		return 2 ;
	else
		return 3 ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>k ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	long long sum = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		val[i] = rand(1 , 1e9) ;
		sum += 1ll * val[i] * k ;
	}
	for(int j = 0 ; j < m ; ++j)
	{
		for(int i = 0 ; i < n ; ++i)
			freq[j][f(arr[i][j])] += val[i] ;
	}
	for(int i = 0 ; i < n ; ++i)
	{
		long long cnt = 0 ;
		for(int j = 0 ; j < m ; ++j)
		{
			for(int c = 0 ; c < 4 ; ++c)
			{
				if(c != f(arr[i][j]))
					cnt += freq[j][c] ;
			}
		}
		if(cnt == sum - val[i] * k)
			return cout<<i+1<<"\n" , 0 ;
	}
	return 0 ;
}

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5824 KB Output is correct
2 Correct 36 ms 7120 KB Output is correct
3 Correct 56 ms 6788 KB Output is correct
4 Correct 11 ms 1744 KB Output is correct
5 Correct 25 ms 7216 KB Output is correct
6 Correct 32 ms 7108 KB Output is correct
7 Correct 26 ms 3464 KB Output is correct
8 Correct 21 ms 3280 KB Output is correct
9 Correct 30 ms 6732 KB Output is correct
10 Correct 46 ms 6568 KB Output is correct
11 Correct 37 ms 5816 KB Output is correct
12 Correct 25 ms 5840 KB Output is correct
13 Correct 30 ms 5808 KB Output is correct
14 Correct 39 ms 4956 KB Output is correct
15 Correct 26 ms 5108 KB Output is correct
16 Correct 28 ms 5096 KB Output is correct
17 Correct 52 ms 6808 KB Output is correct
18 Correct 27 ms 6768 KB Output is correct
19 Correct 45 ms 6736 KB Output is correct
20 Correct 31 ms 6732 KB Output is correct
21 Correct 46 ms 6724 KB Output is correct
22 Correct 54 ms 6740 KB Output is correct
23 Correct 56 ms 6788 KB Output is correct
24 Correct 58 ms 6784 KB Output is correct
25 Correct 33 ms 6748 KB Output is correct
26 Correct 39 ms 6792 KB Output is correct
27 Correct 37 ms 6744 KB Output is correct
28 Correct 37 ms 6764 KB Output is correct
29 Correct 48 ms 6796 KB Output is correct
30 Correct 20 ms 7120 KB Output is correct
31 Correct 31 ms 6992 KB Output is correct
32 Correct 38 ms 7088 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 0 ms 464 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5824 KB Output is correct
2 Correct 36 ms 7120 KB Output is correct
3 Correct 56 ms 6788 KB Output is correct
4 Correct 11 ms 1744 KB Output is correct
5 Correct 25 ms 7216 KB Output is correct
6 Correct 32 ms 7108 KB Output is correct
7 Correct 26 ms 3464 KB Output is correct
8 Correct 21 ms 3280 KB Output is correct
9 Correct 30 ms 6732 KB Output is correct
10 Correct 46 ms 6568 KB Output is correct
11 Correct 37 ms 5816 KB Output is correct
12 Correct 25 ms 5840 KB Output is correct
13 Correct 30 ms 5808 KB Output is correct
14 Correct 39 ms 4956 KB Output is correct
15 Correct 26 ms 5108 KB Output is correct
16 Correct 28 ms 5096 KB Output is correct
17 Correct 52 ms 6808 KB Output is correct
18 Correct 27 ms 6768 KB Output is correct
19 Correct 45 ms 6736 KB Output is correct
20 Correct 31 ms 6732 KB Output is correct
21 Correct 46 ms 6724 KB Output is correct
22 Correct 54 ms 6740 KB Output is correct
23 Correct 56 ms 6788 KB Output is correct
24 Correct 58 ms 6784 KB Output is correct
25 Correct 33 ms 6748 KB Output is correct
26 Correct 39 ms 6792 KB Output is correct
27 Correct 37 ms 6744 KB Output is correct
28 Correct 37 ms 6764 KB Output is correct
29 Correct 48 ms 6796 KB Output is correct
30 Correct 20 ms 7120 KB Output is correct
31 Correct 31 ms 6992 KB Output is correct
32 Correct 38 ms 7088 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 0 ms 464 KB Output is correct
36 Correct 229 ms 31912 KB Output is correct
37 Correct 219 ms 35812 KB Output is correct
38 Correct 325 ms 35480 KB Output is correct
39 Correct 79 ms 12580 KB Output is correct
40 Correct 246 ms 35692 KB Output is correct
41 Correct 131 ms 18192 KB Output is correct
42 Correct 118 ms 18160 KB Output is correct
43 Correct 162 ms 25288 KB Output is correct
44 Correct 199 ms 36164 KB Output is correct
45 Correct 292 ms 36260 KB Output is correct
46 Correct 199 ms 36248 KB Output is correct
47 Correct 236 ms 31944 KB Output is correct
48 Correct 273 ms 31964 KB Output is correct
49 Correct 149 ms 27288 KB Output is correct
50 Correct 225 ms 27156 KB Output is correct
51 Correct 246 ms 30176 KB Output is correct
52 Correct 325 ms 35440 KB Output is correct
53 Correct 312 ms 35420 KB Output is correct
54 Correct 174 ms 33932 KB Output is correct
55 Correct 255 ms 33864 KB Output is correct
56 Correct 165 ms 33864 KB Output is correct
57 Correct 321 ms 35648 KB Output is correct
58 Correct 280 ms 35584 KB Output is correct
59 Correct 216 ms 35256 KB Output is correct
60 Correct 203 ms 35480 KB Output is correct
61 Correct 226 ms 35272 KB Output is correct
62 Correct 209 ms 35116 KB Output is correct
63 Correct 182 ms 35408 KB Output is correct
64 Correct 203 ms 35540 KB Output is correct
65 Correct 297 ms 35284 KB Output is correct
66 Correct 286 ms 35428 KB Output is correct
67 Correct 308 ms 35668 KB Output is correct
68 Correct 236 ms 35416 KB Output is correct
69 Correct 174 ms 35484 KB Output is correct
70 Correct 290 ms 35600 KB Output is correct
71 Correct 249 ms 35248 KB Output is correct
72 Correct 247 ms 35616 KB Output is correct
73 Correct 276 ms 35476 KB Output is correct
74 Correct 0 ms 336 KB Output is correct
75 Correct 0 ms 464 KB Output is correct
76 Correct 0 ms 464 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 0 ms 464 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 46 ms 5824 KB Output is correct
19 Correct 36 ms 7120 KB Output is correct
20 Correct 56 ms 6788 KB Output is correct
21 Correct 11 ms 1744 KB Output is correct
22 Correct 25 ms 7216 KB Output is correct
23 Correct 32 ms 7108 KB Output is correct
24 Correct 26 ms 3464 KB Output is correct
25 Correct 21 ms 3280 KB Output is correct
26 Correct 30 ms 6732 KB Output is correct
27 Correct 46 ms 6568 KB Output is correct
28 Correct 37 ms 5816 KB Output is correct
29 Correct 25 ms 5840 KB Output is correct
30 Correct 30 ms 5808 KB Output is correct
31 Correct 39 ms 4956 KB Output is correct
32 Correct 26 ms 5108 KB Output is correct
33 Correct 28 ms 5096 KB Output is correct
34 Correct 52 ms 6808 KB Output is correct
35 Correct 27 ms 6768 KB Output is correct
36 Correct 45 ms 6736 KB Output is correct
37 Correct 31 ms 6732 KB Output is correct
38 Correct 46 ms 6724 KB Output is correct
39 Correct 54 ms 6740 KB Output is correct
40 Correct 56 ms 6788 KB Output is correct
41 Correct 58 ms 6784 KB Output is correct
42 Correct 33 ms 6748 KB Output is correct
43 Correct 39 ms 6792 KB Output is correct
44 Correct 37 ms 6744 KB Output is correct
45 Correct 37 ms 6764 KB Output is correct
46 Correct 48 ms 6796 KB Output is correct
47 Correct 20 ms 7120 KB Output is correct
48 Correct 31 ms 6992 KB Output is correct
49 Correct 38 ms 7088 KB Output is correct
50 Correct 1 ms 464 KB Output is correct
51 Correct 1 ms 592 KB Output is correct
52 Correct 0 ms 464 KB Output is correct
53 Correct 229 ms 31912 KB Output is correct
54 Correct 219 ms 35812 KB Output is correct
55 Correct 325 ms 35480 KB Output is correct
56 Correct 79 ms 12580 KB Output is correct
57 Correct 246 ms 35692 KB Output is correct
58 Correct 131 ms 18192 KB Output is correct
59 Correct 118 ms 18160 KB Output is correct
60 Correct 162 ms 25288 KB Output is correct
61 Correct 199 ms 36164 KB Output is correct
62 Correct 292 ms 36260 KB Output is correct
63 Correct 199 ms 36248 KB Output is correct
64 Correct 236 ms 31944 KB Output is correct
65 Correct 273 ms 31964 KB Output is correct
66 Correct 149 ms 27288 KB Output is correct
67 Correct 225 ms 27156 KB Output is correct
68 Correct 246 ms 30176 KB Output is correct
69 Correct 325 ms 35440 KB Output is correct
70 Correct 312 ms 35420 KB Output is correct
71 Correct 174 ms 33932 KB Output is correct
72 Correct 255 ms 33864 KB Output is correct
73 Correct 165 ms 33864 KB Output is correct
74 Correct 321 ms 35648 KB Output is correct
75 Correct 280 ms 35584 KB Output is correct
76 Correct 216 ms 35256 KB Output is correct
77 Correct 203 ms 35480 KB Output is correct
78 Correct 226 ms 35272 KB Output is correct
79 Correct 209 ms 35116 KB Output is correct
80 Correct 182 ms 35408 KB Output is correct
81 Correct 203 ms 35540 KB Output is correct
82 Correct 297 ms 35284 KB Output is correct
83 Correct 286 ms 35428 KB Output is correct
84 Correct 308 ms 35668 KB Output is correct
85 Correct 236 ms 35416 KB Output is correct
86 Correct 174 ms 35484 KB Output is correct
87 Correct 290 ms 35600 KB Output is correct
88 Correct 249 ms 35248 KB Output is correct
89 Correct 247 ms 35616 KB Output is correct
90 Correct 276 ms 35476 KB Output is correct
91 Correct 0 ms 336 KB Output is correct
92 Correct 0 ms 464 KB Output is correct
93 Correct 0 ms 464 KB Output is correct
94 Correct 390 ms 34572 KB Output is correct
95 Correct 360 ms 35708 KB Output is correct
96 Correct 611 ms 35776 KB Output is correct
97 Correct 239 ms 19324 KB Output is correct
98 Correct 102 ms 12584 KB Output is correct
99 Correct 291 ms 35724 KB Output is correct
100 Correct 172 ms 18080 KB Output is correct
101 Correct 155 ms 18252 KB Output is correct
102 Correct 167 ms 25380 KB Output is correct
103 Correct 224 ms 36240 KB Output is correct
104 Correct 559 ms 36144 KB Output is correct
105 Correct 604 ms 36268 KB Output is correct
106 Correct 515 ms 34516 KB Output is correct
107 Correct 202 ms 31860 KB Output is correct
108 Correct 197 ms 27192 KB Output is correct
109 Correct 434 ms 31540 KB Output is correct
110 Correct 314 ms 29404 KB Output is correct
111 Correct 301 ms 36296 KB Output is correct
112 Correct 494 ms 35828 KB Output is correct
113 Correct 351 ms 33984 KB Output is correct
114 Correct 141 ms 33828 KB Output is correct
115 Correct 367 ms 33864 KB Output is correct
116 Correct 551 ms 35808 KB Output is correct
117 Correct 539 ms 36196 KB Output is correct
118 Correct 506 ms 35748 KB Output is correct
119 Correct 466 ms 35804 KB Output is correct
120 Correct 548 ms 35988 KB Output is correct
121 Correct 217 ms 31868 KB Output is correct
122 Correct 186 ms 35716 KB Output is correct
123 Correct 308 ms 35480 KB Output is correct
124 Correct 0 ms 464 KB Output is correct
125 Correct 1 ms 464 KB Output is correct
126 Correct 0 ms 464 KB Output is correct