Submission #1231434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231434		wedonttalkanymore	Genetics (BOI18_genetics)	C++20	100 / 100	1774 ms	28184 KiB

genetics

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//#define int long long
#define pii pair <ll, ll>
#define fi first
#define se second

const ll N = 4105, inf = 1e18, mod = 1e9 + 7, block = 320;

int n, m, k;
pair <string, int> a[N];
bitset <N> pre[N][4];

int char_to_int(char x) {
	if (x == 'A') return 0;
	if (x == 'C') return 1;
	if (x == 'G') return 2;
	if (x == 'T') return 3; 
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].fi;
		a[i].se = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		string tmp = a[i].fi;
		for (int j = 0; j < m; j++) {
			pre[i][char_to_int(tmp[j])][j] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		bool check = true;
		int t = (i >= n / 2);
		if (t) {
			for (int j = i + 1; j <= n; j++) {
				int sum = 0;
				for (int x = 0; x < 4; x++) {
					int diff = (pre[i][x] ^ pre[j][x]).count();
					sum += diff;
				}
				sum /= 2;
				if (sum != k) {
					check = false;
					break;
				}
			}
			if (!check) continue;
			for (int j = 1; j < i; j++) {
				int sum = 0;
				for (int x = 0; x < 4; x++) {
					int diff = (pre[i][x] ^ pre[j][x]).count();
					sum += diff;
				}
				sum /= 2;
				if (sum != k) {
					check = false;
					break;
				}
			}
			if (check) {
				cout << a[i].se << '\n';
				break;
			}
		}
		else {
			for (int j = n; j > i; j--) {
				int sum = 0;
				for (int x = 0; x < 4; x++) {
					int diff = (pre[i][x] ^ pre[j][x]).count();
					sum += diff;
				}
				sum /= 2;
				if (sum != k) {
					check = false;
					break;
				}
			}
			if (!check) continue;
			for (int j = i - 1; j >= 1; j--) {
				int sum = 0;
				for (int x = 0; x < 4; x++) {
					int diff = (pre[i][x] ^ pre[j][x]).count();
					sum += diff;
				}
				sum /= 2;
				if (sum != k) {
					check = false;
					break;
				}
			}
			if (check) {
				cout << a[i].se << '\n';
				break;
			}
		}
	}
	return 0;
}

Compilation message (stderr)

genetics.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
genetics.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
genetics.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
genetics.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
genetics.cpp:64:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   64 | int char_to_int(char x) {
      |                       ^
genetics.cpp:64:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
genetics.cpp:64:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
genetics.cpp:64:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
genetics.cpp:71:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   71 | signed main() {
      |             ^
genetics.cpp:71:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
genetics.cpp:71:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
genetics.cpp:71:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
genetics.cpp: In function 'int char_to_int(char)':
genetics.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

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