oj.uz

답안 #68362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68362 2018-08-16T20:03:13 Z Pajaraja Genetics (BOI18_genetics) C++17
27 / 100
 118 ms 33272 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<400000;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/2;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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1144 KB Output is correct
2 Correct 26 ms 1272 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 25 ms 1016 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct
6 Correct 16 ms 1272 KB Output is correct
7 Correct 26 ms 760 KB Output is correct
8 Correct 21 ms 376 KB Output is correct
9 Correct 22 ms 888 KB Output is correct
10 Correct 25 ms 1144 KB Output is correct
11 Correct 19 ms 1144 KB Output is correct
12 Correct 25 ms 1272 KB Output is correct
13 Correct 19 ms 1272 KB Output is correct
14 Correct 27 ms 1272 KB Output is correct
15 Correct 27 ms 1272 KB Output is correct
16 Correct 22 ms 1144 KB Output is correct
17 Correct 22 ms 504 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 33272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 33272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1144 KB Output is correct
2 Correct 26 ms 1272 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 25 ms 1016 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct
6 Correct 16 ms 1272 KB Output is correct
7 Correct 26 ms 760 KB Output is correct
8 Correct 21 ms 376 KB Output is correct
9 Correct 22 ms 888 KB Output is correct
10 Correct 25 ms 1144 KB Output is correct
11 Correct 19 ms 1144 KB Output is correct
12 Correct 25 ms 1272 KB Output is correct
13 Correct 19 ms 1272 KB Output is correct
14 Correct 27 ms 1272 KB Output is correct
15 Correct 27 ms 1272 KB Output is correct
16 Correct 22 ms 1144 KB Output is correct
17 Correct 22 ms 504 KB Output is correct
18 Incorrect 118 ms 33272 KB Output isn't correct
19 Halted 0 ms 0 KB -