oj.uz

Submission #68358

# Submission time Handle Problem Language Result Execution time Memory
68358 2018-08-16T19:54:42 Z Pajaraja Genetics (BOI18_genetics) C++17
46 / 100
 949 ms 155572 KB 
#include <bits/stdc++.h>
using namespace std;
int uc[4][4107],k,m;
long long arr[4107][4107],ars[4107][1000];
bool c[4107],ps;
bool check(int a,int b)
{
	int x=0;
	for(int i=0;i<=(ps?(m-1)/16:(m-1)/64);i++) x+=__builtin_popcountll(ars[a][i] xor ars[b][i]);
	if(ps) x/=2;
	if(x==k) return true;
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n>>m>>k;
	string s;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		for(int j=0;j<m;j++)
		{
			if(s[j]=='A') arr[i][j]=0;
			if(s[j]=='C') arr[i][j]=1;
			if(s[j]=='G') arr[i][j]=2;
			if(s[j]=='T') arr[i][j]=3;
			if(arr[i][j]>1) ps=true;
			uc[arr[i][j]][j]++;
		}
	}
	if(!ps) for(int i=0;i<n;i++) for(int j=0;j<m;j++) ars[i][j/64]+=(arr[i][j]<<(j%64)); 
	else for(int i=0;i<n;i++) for(int j=0;j<m;j++) ars[i][j/16]+=(1LL<<(arr[i][j]+(j%16)*4));
	for(int ttt=0;ttt<1000000;ttt++)
	{
		int x=rand()%n,y=rand()%n;
		if(x==y) continue;
		int st=0;
		if(!check(x,y)) {c[x]=c[y]=true;};
	}
	for(int i=0;i<n;i++) if(!c[i])
	{
		int skor=0;
		bool propo=false;
		for(int j=0;j<m;j++) skor+=(n-uc[arr[i][j]][j]);
		if(skor!=(n-1)*k) continue;
		for(int j=0;j<n;j++) if(i!=j) if(!check(i,j)) {propo=true; break;}
		if(propo) continue;
		printf("%d",i+1);
		return 0;
	}
}

Compilation message

genetics.cpp: In function 'int main()':
genetics.cpp:39:7: warning: unused variable 'st' [-Wunused-variable]
   int st=0;
       ^~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1272 KB Output is correct
2 Correct 58 ms 1272 KB Output is correct
3 Correct 42 ms 376 KB Output is correct
4 Correct 53 ms 1016 KB Output is correct
5 Correct 46 ms 1144 KB Output is correct
6 Correct 39 ms 1144 KB Output is correct
7 Correct 87 ms 888 KB Output is correct
8 Correct 51 ms 376 KB Output is correct
9 Correct 50 ms 888 KB Output is correct
10 Correct 56 ms 1144 KB Output is correct
11 Correct 38 ms 1144 KB Output is correct
12 Correct 54 ms 1276 KB Output is correct
13 Correct 42 ms 1272 KB Output is correct
14 Correct 59 ms 1272 KB Output is correct
15 Correct 60 ms 1272 KB Output is correct
16 Correct 43 ms 1144 KB Output is correct
17 Correct 45 ms 508 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 35320 KB Output is correct
2 Correct 217 ms 42872 KB Output is correct
3 Correct 227 ms 40952 KB Output is correct
4 Correct 94 ms 15608 KB Output is correct
5 Correct 234 ms 42872 KB Output is correct
6 Correct 228 ms 42872 KB Output is correct
7 Correct 171 ms 18808 KB Output is correct
8 Correct 159 ms 18976 KB Output is correct
9 Correct 216 ms 40184 KB Output is correct
10 Correct 220 ms 40184 KB Output is correct
11 Correct 209 ms 35448 KB Output is correct
12 Correct 206 ms 35576 KB Output is correct
13 Correct 205 ms 35448 KB Output is correct
14 Correct 191 ms 30588 KB Output is correct
15 Correct 187 ms 30844 KB Output is correct
16 Correct 189 ms 31992 KB Output is correct
17 Correct 232 ms 41208 KB Output is correct
18 Correct 227 ms 40952 KB Output is correct
19 Correct 226 ms 41080 KB Output is correct
20 Correct 225 ms 40696 KB Output is correct
21 Correct 220 ms 41080 KB Output is correct
22 Correct 228 ms 40824 KB Output is correct
23 Correct 232 ms 41008 KB Output is correct
24 Correct 228 ms 40952 KB Output is correct
25 Correct 233 ms 40696 KB Output is correct
26 Correct 235 ms 41080 KB Output is correct
27 Correct 226 ms 40696 KB Output is correct
28 Correct 236 ms 40696 KB Output is correct
29 Correct 228 ms 40952 KB Output is correct
30 Correct 207 ms 42872 KB Output is correct
31 Correct 224 ms 42876 KB Output is correct
32 Correct 223 ms 42872 KB Output is correct
33 Correct 47 ms 376 KB Output is correct
34 Correct 42 ms 1272 KB Output is correct
35 Correct 46 ms 504 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 35320 KB Output is correct
2 Correct 217 ms 42872 KB Output is correct
3 Correct 227 ms 40952 KB Output is correct
4 Correct 94 ms 15608 KB Output is correct
5 Correct 234 ms 42872 KB Output is correct
6 Correct 228 ms 42872 KB Output is correct
7 Correct 171 ms 18808 KB Output is correct
8 Correct 159 ms 18976 KB Output is correct
9 Correct 216 ms 40184 KB Output is correct
10 Correct 220 ms 40184 KB Output is correct
11 Correct 209 ms 35448 KB Output is correct
12 Correct 206 ms 35576 KB Output is correct
13 Correct 205 ms 35448 KB Output is correct
14 Correct 191 ms 30588 KB Output is correct
15 Correct 187 ms 30844 KB Output is correct
16 Correct 189 ms 31992 KB Output is correct
17 Correct 232 ms 41208 KB Output is correct
18 Correct 227 ms 40952 KB Output is correct
19 Correct 226 ms 41080 KB Output is correct
20 Correct 225 ms 40696 KB Output is correct
21 Correct 220 ms 41080 KB Output is correct
22 Correct 228 ms 40824 KB Output is correct
23 Correct 232 ms 41008 KB Output is correct
24 Correct 228 ms 40952 KB Output is correct
25 Correct 233 ms 40696 KB Output is correct
26 Correct 235 ms 41080 KB Output is correct
27 Correct 226 ms 40696 KB Output is correct
28 Correct 236 ms 40696 KB Output is correct
29 Correct 228 ms 40952 KB Output is correct
30 Correct 207 ms 42872 KB Output is correct
31 Correct 224 ms 42876 KB Output is correct
32 Correct 223 ms 42872 KB Output is correct
33 Correct 47 ms 376 KB Output is correct
34 Correct 42 ms 1272 KB Output is correct
35 Correct 46 ms 504 KB Output is correct
36 Correct 949 ms 136056 KB Output is correct
37 Correct 658 ms 155256 KB Output is correct
38 Correct 675 ms 150980 KB Output is correct
39 Correct 292 ms 78584 KB Output is correct
40 Correct 677 ms 154172 KB Output is correct
41 Correct 474 ms 79608 KB Output is correct
42 Correct 452 ms 79736 KB Output is correct
43 Correct 538 ms 127716 KB Output is correct
44 Correct 635 ms 154660 KB Output is correct
45 Correct 735 ms 154736 KB Output is correct
46 Correct 688 ms 155572 KB Output is correct
47 Execution timed out 212 ms 108536 KB Time limit exceeded (wall clock)
48 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1272 KB Output is correct
2 Correct 58 ms 1272 KB Output is correct
3 Correct 42 ms 376 KB Output is correct
4 Correct 53 ms 1016 KB Output is correct
5 Correct 46 ms 1144 KB Output is correct
6 Correct 39 ms 1144 KB Output is correct
7 Correct 87 ms 888 KB Output is correct
8 Correct 51 ms 376 KB Output is correct
9 Correct 50 ms 888 KB Output is correct
10 Correct 56 ms 1144 KB Output is correct
11 Correct 38 ms 1144 KB Output is correct
12 Correct 54 ms 1276 KB Output is correct
13 Correct 42 ms 1272 KB Output is correct
14 Correct 59 ms 1272 KB Output is correct
15 Correct 60 ms 1272 KB Output is correct
16 Correct 43 ms 1144 KB Output is correct
17 Correct 45 ms 508 KB Output is correct
18 Correct 221 ms 35320 KB Output is correct
19 Correct 217 ms 42872 KB Output is correct
20 Correct 227 ms 40952 KB Output is correct
21 Correct 94 ms 15608 KB Output is correct
22 Correct 234 ms 42872 KB Output is correct
23 Correct 228 ms 42872 KB Output is correct
24 Correct 171 ms 18808 KB Output is correct
25 Correct 159 ms 18976 KB Output is correct
26 Correct 216 ms 40184 KB Output is correct
27 Correct 220 ms 40184 KB Output is correct
28 Correct 209 ms 35448 KB Output is correct
29 Correct 206 ms 35576 KB Output is correct
30 Correct 205 ms 35448 KB Output is correct
31 Correct 191 ms 30588 KB Output is correct
32 Correct 187 ms 30844 KB Output is correct
33 Correct 189 ms 31992 KB Output is correct
34 Correct 232 ms 41208 KB Output is correct
35 Correct 227 ms 40952 KB Output is correct
36 Correct 226 ms 41080 KB Output is correct
37 Correct 225 ms 40696 KB Output is correct
38 Correct 220 ms 41080 KB Output is correct
39 Correct 228 ms 40824 KB Output is correct
40 Correct 232 ms 41008 KB Output is correct
41 Correct 228 ms 40952 KB Output is correct
42 Correct 233 ms 40696 KB Output is correct
43 Correct 235 ms 41080 KB Output is correct
44 Correct 226 ms 40696 KB Output is correct
45 Correct 236 ms 40696 KB Output is correct
46 Correct 228 ms 40952 KB Output is correct
47 Correct 207 ms 42872 KB Output is correct
48 Correct 224 ms 42876 KB Output is correct
49 Correct 223 ms 42872 KB Output is correct
50 Correct 47 ms 376 KB Output is correct
51 Correct 42 ms 1272 KB Output is correct
52 Correct 46 ms 504 KB Output is correct
53 Correct 949 ms 136056 KB Output is correct
54 Correct 658 ms 155256 KB Output is correct
55 Correct 675 ms 150980 KB Output is correct
56 Correct 292 ms 78584 KB Output is correct
57 Correct 677 ms 154172 KB Output is correct
58 Correct 474 ms 79608 KB Output is correct
59 Correct 452 ms 79736 KB Output is correct
60 Correct 538 ms 127716 KB Output is correct
61 Correct 635 ms 154660 KB Output is correct
62 Correct 735 ms 154736 KB Output is correct
63 Correct 688 ms 155572 KB Output is correct
64 Execution timed out 212 ms 108536 KB Time limit exceeded (wall clock)
65 Halted 0 ms 0 KB -