Submission #1215496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215496		boclobanchat	Genetics (BOI18_genetics)	C++20	46 / 100	2093 ms	18504 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
mt19937_64 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 MAXN=4114;
bitset<MAXN> bt[MAXN][2];
bool ck[MAXN],cs[MAXN][MAXN];
int vi[MAXN];
int get(int x,int y)
{
	return ((bt[x][0]^bt[y][0])|(bt[x][1]^bt[y][1])).count();
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    int cnt=n;
    for(int i=1;i<=n;i++)
    {
    	string s;
    	cin>>s;
    	for(int j=0;j<m;j++)
    	{
    		if(s[j]=='A'||s[j]=='C') bt[i][0][j]=1;
    		if(s[j]=='A'||s[j]=='G') bt[i][1][j]=1;
		}
	}
	for(int i=1;i<=n;i++) cs[i][i]=true,vi[i]=i;
	while(cnt>1)
	{
		int pcnt=cnt;
		int l=Rand(1,cnt),r=Rand(1,n);
		while(cs[vi[l]][r]) l=Rand(1,cnt),r=Rand(1,n);
		l=vi[l];
		cs[l][r]=cs[r][l]=true;
		if(get(l,r)!=k)
		{
			if(!ck[l]) ck[l]=true,cnt--;
			if(!ck[r]) ck[r]=true,cnt--;
		}
		if(pcnt!=cnt)
		{
			cnt=0;
			for(int j=1;j<=n;j++) if(!ck[j]) vi[++cnt]=j;
		}
	}
	for(int i=1;i<=n;i++) if(!ck[i]) return cout<<i,0;
}

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26