Submission #378353

#	Time	Username	Problem	Language	Result	Execution time	Memory
378353		soroush	Genetics (BOI18_genetics)	C++17	100 / 100	1200 ms	93000 KiB

genetics

//*
#pragma GCC optimize("O2")
//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

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

const int maxn = 4110;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , k;
char s[maxn][maxn];
bool bad[maxn];
int cnt[4][maxn];
bitset < maxn > a[4][maxn];
int diff[maxn][maxn];
std::chrono::duration<double> elapsed_seconds;

int Diff(int i , int j){
	if(diff[i][j] ^ -1)return diff[i][j];
	diff[i][j] = m;
	for(int k = 0 ; k < 4 ; k ++)
		diff[i][j] -= (a[k][i] & a[k][j]).count();
	diff[j][i] = diff[i][j];
	return diff[i][j];
}

void chk(int i){
	if(bad[i])return;
	if(elapsed_seconds.count() > 0.9){
		for(int j = 1 ; j <= n ; j ++)if(j^i){
			if(Diff(i , j) ^ k){
				bad[i] = bad[j] = 1;return;}
		}
	}
	else{
		for(int j = n ; j >= 1 ; j --)if(j^i){
			if(Diff(i , j) ^ k){
				bad[i] = bad[j] = 1;return;}
		}
	}
	dokme(i);
}

void add(int i){
	for(int j = 0 ; j < m ; j ++){
		if(s[i][j] == 'A')cnt[0][j]-- , a[0][i][j] = 1;
		else if(s[i][j] == 'T')cnt[1][j]-- , a[1][i][j] = 1;
		else if(s[i][j] == 'C')cnt[2][j]-- , a[2][i][j] = 1;
		else cnt[3][j]-- , a[3][i][j] = 1;
	}
}


int32_t main(){
	std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
	cin >> n >> m >> k;
	ms(diff , -1);
	for(int i = 0 ; i < m ; i ++)for(int j = 0 ; j < 4 ; j ++)cnt[j][i] = n;
	for(int i = 1 ; i <= n ; i ++)scanf("%s",s + i) , add(i);
	for(int i = n ; i >= 1 ; i --)if(!bad[i]){
		int sum = 0;
		for(int j = 0 ; j < m ; j ++){
			if(s[i][j] == 'A')sum += cnt[0][j];
			else if(s[i][j] == 'T')sum += cnt[1][j];
			else if(s[i][j] == 'C')sum += cnt[2][j];
			else sum += cnt[3][j];
		}
		if(sum == k * (n - 1))chk(i);
		end = std::chrono::system_clock::now();
		elapsed_seconds = end-start;
		if(elapsed_seconds.count() > 0.9)break;
	}
	for(int i = 1 ; i <= n ; i ++)if(!bad[i]){
		int sum = 0;
		for(int j = 0 ; j < m ; j ++){
			if(s[i][j] == 'A')sum += cnt[0][j];
			else if(s[i][j] == 'T')sum += cnt[1][j];
			else if(s[i][j] == 'C')sum += cnt[2][j];
			else sum += cnt[3][j];
		}
		if(sum == k * (n - 1))chk(i);
	}
	return(0);
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:78:40: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[4110]' [-Wformat=]
   78 |  for(int i = 1 ; i <= n ; i ++)scanf("%s",s + i) , add(i);
      |                                       ~^  ~~~~~
      |                                        |    |
      |                                        |    char (*)[4110]
      |                                        char*
genetics.cpp:78:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |  for(int i = 1 ; i <= n ; i ++)scanf("%s",s + i) , add(i);
      |                                ~~~~~^~~~~~~~~~~~

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