Submission #532700

#	Time	Username	Problem	Language	Result	Execution time	Memory
532700		fatemetmhr	Genetics (BOI18_genetics)	C++17	Compilation error	0 ms	0 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


const int maxn5 = 5e3 + 10;


string s;
bitset <4105> a[maxn5], tmp;
int av[maxn5], per[maxn5];
int n, m, k, sz;

inline bool ok(int i, int j){
	if(n * m <= 700 * 700){
		int cnt = 0;
		for(int z = 0; z < m && cnt <= k; z++)
			cnt += (s[i][z] != s[j][z]);
		return cnt == k;
	}
	tmp = a[i] ^ a[j];
	//cout << i << ' ' << j << ' ' << tmp.count() << endl;
	return tmp.count() == k;
}

inline void rem(int v){
	//cout << "removing " << v << endl;
	bool re = false;
	for(int i = 0; i < sz; i++){
		if(re)
			per[i - 1] = per[i];
		if(per[i] == v)
			re = true;
	}
	if(re)
		sz--;
	//cout << sz << endl;
}

inline void check(int v){
	for(int i = 0; i < n; i++)
		av[i] = i;
	shuffle(av, av + n, rng);
	for(int i = 0; i < n; i++) 
		if(v != av[i] && !ok(v, av[i])){
			rem(av[i]);
			return;
		}
	cout << v + 1 << endl;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		cin >> s[i];
		for(int j = 0; j < m; j++)
			if(s[i][j] == 'A')
				a[i][j] = 1;
		per[i] = i;
	}

	sz = n;
	while(true){
		int v = per[rng() % sz];
		check(v);
		rem(v);
	}

}

Compilation message (stderr)

genetics.cpp: In function 'bool ok(int, int)':
genetics.cpp:24:16: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<char>, char>::value_type {aka char}[int]' for array subscript
   24 |    cnt += (s[i][z] != s[j][z]);
      |                ^
genetics.cpp:24:27: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<char>, char>::value_type {aka char}[int]' for array subscript
   24 |    cnt += (s[i][z] != s[j][z]);
      |                           ^
genetics.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  return tmp.count() == k;
      |         ~~~~~~~~~~~~^~~~
genetics.cpp: In function 'int main()':
genetics.cpp:66:11: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<char>, char>::value_type {aka char}[int]' for array subscript
   66 |    if(s[i][j] == 'A')
      |           ^