Submission #1248368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248368		liangjeremy	Genetics (BOI18_genetics)	C++20	19 / 100	1071 ms	18244 KiB

genetics

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using db=double;
using sll=__int128;
using lb=long double; 
 
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    int n,m,k; cin>>n>>m>>k; vector<string>a(n+1);
    for(int i=1; i<=n; i++){ cin>>a[i]; }
    const int MAXN=1805; vector<bitset<MAXN>>A(n+1);
    for(int i=1; i<=n; i++){
    	for(int j=0; j<m; j++){
    		if(a[i][j]=='A')A[i][j]=1; 
    	}
    }
    int ans=-1;
    for(int i=1; i<=n; i++){
    	bool ok=true;
    	for(int j=1; j<=n; j++){
    		if(i==j)continue; 
    		if((A[i]^A[j]).count()!=k)ok=false;
    	}
    	if(ok)ans=i;
    }
    cout<<ans<<'\n'; 
}

/*
O what can ail thee, knight-at-arms,
       Alone and palely loitering?
The sedge has withered from the lake,
       And no birds sing.
 
O what can ail thee, knight-at-arms,
       So haggard and so woe-begone?
The squirrel’s granary is full,
       And the harvest’s done.
 
I see a lily on thy brow,
       With anguish moist and fever-dew,
And on thy cheeks a fading rose
       Fast withereth too. 
*/

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