Submission #163083

#	Time	Username	Problem	Language	Result	Execution time	Memory
163083		nvmdava	Genetics (BOI18_genetics)	C++17	46 / 100	2096 ms	74116 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define N 1000005
 
char c;
 
ll val[4500][70];
ll val2[4500][70];
int to[500];
int to2[500];
vector<int> v, w;
int n, m, k, p;
 
int ans[4200][4200];
 
inline bool comp(int a, int b){
	if(ans[a][b] != -1)
		return ans[a][b];
	int q = 0;
	for(int j = 0; j <= 65; ++j){
		q += __builtin_popcountll((val[a][j] ^ val[b][j]) | (val2[a][j] ^ val2[b][j]));
		if(q > k){
			ans[a][b] = 0;
			ans[b][a] = 0;
			return 0;
		}
	}
	ans[a][b] = (q == k);
	ans[b][a] = (q == k);
	return ans[a][b];
}
 
int main(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	// ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	memset(ans, -1, sizeof ans);
	to['A'] = 0; to2['A'] = 1;
	to['C'] = 1; to2['C'] = 1;
	to['G'] = 0; to2['G'] = 0;
	to['T'] = 1; to2['T'] = 0;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i){
		v.push_back(i);
		getchar();
		for(int j = 0; j < m; ++j){
			c = getchar();
			val[i][j / 64] |= ((1LL * to[(int)c]) << (j % 64));
			val2[i][j / 64] |= ((1LL * to2[(int)c]) << (j % 64));
		}
	}
	random_shuffle(v.begin(), v.end());
	while(true){
		int i;
		for(i = v.size() - 1; i > 0; --i){
			if(!comp(v[i], v[0])){
				swap(v[i], v.back());
				w.push_back(v.back());
				v.pop_back();
				swap(v[0], v.back());
				w.push_back(v.back());
				v.pop_back();
				break;
			}
		}
		if(i)
			continue;
		bool ok = 1;
		for(int& i : w){
			if(!comp(v[0], i)){
				ok = 0;
				swap(v[0], v.back());
				w.push_back(v.back());
				v.pop_back();
				break;
			}
		}
		if(ok){
			cout<<v[0];
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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