Submission #1127726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127726		nguyenphong233	Genetics (BOI18_genetics)	C++20	100 / 100	235 ms	132360 KiB

genetics

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)4100 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

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

long long Rand(long long l,long long r){
    long long x = rng() % (long long)1e18;
    return x % (r - l + 1) + l;
}

int a[MAX][MAX],w[MAX],valid[MAX];
int toin(char s){
	if(s == 'A')return 0;
	if(s == 'C')return 1;
	if(s == 'T')return 2;
	if(s == 'G')return 3;
}
signed main(){

	read();
	
	int n,m,k;

	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++){
		string s;
		cin >> s;
		for(int j = 0;j < m;j++)a[i][j + 1] = toin(s[j]);
		valid[i] = 1;
	}	
	
	int candidate = n;
	while(candidate > 1){
		
		int total = 0;
		for(int i = 1;i <= n;i++){
			w[i] = Rand(1,1e3);
			total += w[i];
		}
		vector<vector<int>> sumcol(4,vector<int>(m + 5,0));
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= m;j++){
				sumcol[a[i][j]][j] += w[i];
			}
		}
		
		// hash : a[i] = w[i];
		// if row i-th is the answer: the constraint: k * (total - w[i]) -> mean other hash of j-th row must be display k times
		// it should be equal to sum of all (total - sumcol[col[j]][j]) -> mean the sum hash of color that different from i-th row must contribute to weight
		// if it is equal -> it is true.. 
		
		for(int i = 1;i <= n;i++){
			if(!valid[i])continue;
			int sum = 0;
			for(int j = 1;j <= m;j++){
				sum += total - sumcol[a[i][j]][j];
			}
			if(sum != (total - w[i]) * k){
				candidate--;
				valid[i] = 0;
			}
		}		
	}
	
	for(int i = 1;i <= n;i++)if(valid[i])return cout << i << '\n',0;
	
	
	
}

Compilation message (stderr)

genetics.cpp: In function 'long long int toin(char)':
genetics.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^

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