답안 #105893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105893	2019-04-15T15:12:51 Z	Pajaraja	Genetics (BOI18_genetics)	C++17	0 / 100	107 ms	41596 KB

genetics

#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));
	int x=0,y=1;
	mt19937 rng(11122000);
	/*for(int ttt=0;ttt<400000;ttt++)
	{
		x=uniform_int_distribution<int>(0, n-1)(rng),y=uniform_int_distribution<int>(0,n-1)(rng);
		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 i=0;i<20;i++) 
		{
			y=uniform_int_distribution<int>(0, n-1)(rng);
			if(i==y) continue;
			if(!check(i,y)) {c[i]=c[y]=true;}
		}
		if(c[i]) continue;
		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:35:6: warning: unused variable 'x' [-Wunused-variable]
  int x=0,y=1;
      ^

Subtask #1
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1144 KB	Output is correct
2	Correct	5 ms	1272 KB	Output is correct
3	Correct	5 ms	372 KB	Output is correct
4	Correct	5 ms	1016 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	5 ms	1144 KB	Output is correct
7	Correct	5 ms	760 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	888 KB	Output is correct
10	Correct	5 ms	1272 KB	Output is correct
11	Correct	6 ms	1144 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Correct	5 ms	1272 KB	Output is correct
14	Correct	6 ms	1276 KB	Output is correct
15	Correct	5 ms	1272 KB	Output is correct
16	Correct	5 ms	1144 KB	Output is correct
17	Incorrect	5 ms	376 KB	Output isn't correct

Subtask #2
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	34040 KB	Output is correct
2	Correct	65 ms	41464 KB	Output is correct
3	Correct	76 ms	39676 KB	Output is correct
4	Correct	25 ms	15352 KB	Output is correct
5	Correct	70 ms	41592 KB	Output is correct
6	Correct	73 ms	41592 KB	Output is correct
7	Correct	36 ms	18168 KB	Output is correct
8	Correct	35 ms	18296 KB	Output is correct
9	Correct	66 ms	38904 KB	Output is correct
10	Correct	106 ms	38904 KB	Output is correct
11	Correct	74 ms	34168 KB	Output is correct
12	Correct	61 ms	34552 KB	Output is correct
13	Correct	65 ms	34296 KB	Output is correct
14	Correct	66 ms	29560 KB	Output is correct
15	Correct	56 ms	29920 KB	Output is correct
16	Correct	54 ms	31096 KB	Output is correct
17	Correct	73 ms	39800 KB	Output is correct
18	Correct	65 ms	39672 KB	Output is correct
19	Correct	73 ms	39936 KB	Output is correct
20	Correct	67 ms	39416 KB	Output is correct
21	Correct	72 ms	39800 KB	Output is correct
22	Correct	78 ms	39544 KB	Output is correct
23	Correct	79 ms	39672 KB	Output is correct
24	Correct	78 ms	39672 KB	Output is correct
25	Correct	68 ms	39416 KB	Output is correct
26	Correct	73 ms	39672 KB	Output is correct
27	Correct	71 ms	39528 KB	Output is correct
28	Correct	70 ms	39544 KB	Output is correct
29	Correct	72 ms	39672 KB	Output is correct
30	Correct	57 ms	41592 KB	Output is correct
31	Correct	58 ms	41596 KB	Output is correct
32	Correct	70 ms	41592 KB	Output is correct
33	Correct	6 ms	376 KB	Output is correct
34	Correct	5 ms	1272 KB	Output is correct
35	Incorrect	5 ms	376 KB	Output isn't correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	34040 KB	Output is correct
2	Correct	65 ms	41464 KB	Output is correct
3	Correct	76 ms	39676 KB	Output is correct
4	Correct	25 ms	15352 KB	Output is correct
5	Correct	70 ms	41592 KB	Output is correct
6	Correct	73 ms	41592 KB	Output is correct
7	Correct	36 ms	18168 KB	Output is correct
8	Correct	35 ms	18296 KB	Output is correct
9	Correct	66 ms	38904 KB	Output is correct
10	Correct	106 ms	38904 KB	Output is correct
11	Correct	74 ms	34168 KB	Output is correct
12	Correct	61 ms	34552 KB	Output is correct
13	Correct	65 ms	34296 KB	Output is correct
14	Correct	66 ms	29560 KB	Output is correct
15	Correct	56 ms	29920 KB	Output is correct
16	Correct	54 ms	31096 KB	Output is correct
17	Correct	73 ms	39800 KB	Output is correct
18	Correct	65 ms	39672 KB	Output is correct
19	Correct	73 ms	39936 KB	Output is correct
20	Correct	67 ms	39416 KB	Output is correct
21	Correct	72 ms	39800 KB	Output is correct
22	Correct	78 ms	39544 KB	Output is correct
23	Correct	79 ms	39672 KB	Output is correct
24	Correct	78 ms	39672 KB	Output is correct
25	Correct	68 ms	39416 KB	Output is correct
26	Correct	73 ms	39672 KB	Output is correct
27	Correct	71 ms	39528 KB	Output is correct
28	Correct	70 ms	39544 KB	Output is correct
29	Correct	72 ms	39672 KB	Output is correct
30	Correct	57 ms	41592 KB	Output is correct
31	Correct	58 ms	41596 KB	Output is correct
32	Correct	70 ms	41592 KB	Output is correct
33	Correct	6 ms	376 KB	Output is correct
34	Correct	5 ms	1272 KB	Output is correct
35	Incorrect	5 ms	376 KB	Output isn't correct

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1144 KB	Output is correct
2	Correct	5 ms	1272 KB	Output is correct
3	Correct	5 ms	372 KB	Output is correct
4	Correct	5 ms	1016 KB	Output is correct
5	Correct	6 ms	1144 KB	Output is correct
6	Correct	5 ms	1144 KB	Output is correct
7	Correct	5 ms	760 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	888 KB	Output is correct
10	Correct	5 ms	1272 KB	Output is correct
11	Correct	6 ms	1144 KB	Output is correct
12	Correct	5 ms	1272 KB	Output is correct
13	Correct	5 ms	1272 KB	Output is correct
14	Correct	6 ms	1276 KB	Output is correct
15	Correct	5 ms	1272 KB	Output is correct
16	Correct	5 ms	1144 KB	Output is correct
17	Incorrect	5 ms	376 KB	Output isn't correct

답안 #105893

Compilation message

Subtask #1 0 / 27.0

Subtask #2 0 / 19.0

Subtask #3 0 / 28.0

Subtask #4 0 / 26.0

Subtask #1
0 / 27.0

Subtask #2
0 / 19.0

Subtask #3
0 / 28.0

Subtask #4
0 / 26.0