Submission #1034592

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10345922024-07-25 15:13:55anangoGenetics (BOI18_genetics)C++17
27 / 100
959 ms3164 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng;
int INF = 1LL<<30;
int n,m,k;
int isvalid(int a, int b) {
//is a/b close enough to k/m (statistically)
if (b<400) return 1; //small sample size
int maxdelta = sqrt(b)+2;
maxdelta*=(b+m);
int realdelta = abs(b*k-a*m);
return realdelta<=maxdelta;
}
int match(string &s1, string &s2) {
int ct=0;
for (int i=0; i<m; i++) {
ct+=s1[i]!=s2[i];
if (!isvalid(ct,i+1)) return -1;
}
return ct;
}
signed main() {
/*#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...