Submission #658350

#	Time	Username	Problem	Language	Result	Execution time	Memory
658350		inksamurai	Genetics (BOI18_genetics)	C++17	19 / 100	2045 ms	2764 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3NRqilq ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());

const int _n=4100;

pair<bitset<_n>,int> a[_n];

signed main(){
_3NRqilq;
	int n,m,k;
	cin>>n>>m>>k;
	rep(i,n){
		string s;
		cin>>s;
		rep(j,sz(s)){
			if(s[j]=='C'){
				a[i].fi[j]=1;
			}
		}
		a[i].se=i;
	}
	// srand(time(nullptr));
	shuffle(a,a+n,mrand);
	rep(i,n){
		bool pok=1;
		// print(a[i].fi);
		rep(j,n/2+1){
			if(j!=i and (a[i].fi^a[j].fi).count()!=k){
				pok=0;
				break;
			}
			if(n-1-j!=i and (a[i].fi^a[n-1-j].fi).count()!=k){
				pok=0;
				break;
			}
		}
		if(pok){
			print(a[i].se+1);
			return 0;
		}
	}
	print(-1);
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:45:41: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |    if(j!=i and (a[i].fi^a[j].fi).count()!=k){
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
genetics.cpp:49:49: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |    if(n-1-j!=i and (a[i].fi^a[n-1-j].fi).count()!=k){
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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