Submission #163079

#	Time	Username	Problem	Language	Result	Execution time	Memory
163079		nvmdava	Genetics (BOI18_genetics)	C++17	100 / 100	854 ms	40056 KiB

genetics

#include <bits/stdc++.h>
// #pragma GCC optimize("unroll-loops,Ofast")
#pragma GCC target("fma")
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];
bool ans[4200][4200];
bool vis[4200][4200];
bool ok[4200];
int n, m, k;
inline bool comp(int a, int b){
	if(vis[a][b])
		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]));
	
	vis[a][b] = vis[b][a] = 1;
	return ans[a][b] = ans[b][a] = (q == k);
}
 
int main(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	// ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	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);
	int i, j;
	for(i = 1; i <= n; ++i){
		getchar();
		for(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));
		}
	}
 
	for(i = 1; i <= n; ++i){
		if(ok[i]) continue;
		for(j = i + 1; j <= n; ++j){
			if(!comp(i, j)){
				ok[i] = ok[j] = 1;
				break;
			}
		}
		if(ok[i])
			continue;
		for(j = 1; j < i; ++j){
			if(!comp(i, j)){
				ok[i] = 1;
				break;
			}
		}
		if(!ok[i]){
			cout<<i;
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:40: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: 28 / 28
• Subtask 4: 26 / 26