제출 #1034612

#제출 시각아이디문제언어결과실행 시간메모리
1034612anangoGenetics (BOI18_genetics)C++17
0 / 100
40 ms5364 KiB
#include <bits/stdc++.h> #define int long long using namespace std; mt19937 rng; int INF = 1LL<<30; int n,m,k; int match(string &s1, string &s2) { int ct=0; int b = 0; long double prob = 1; for (int i=0; i<m; i++) { bool bol = s1[i]!=s2[i]; //ct and b, k and n if (bol) { prob*=k; prob/=n; prob*=b+1; prob/=ct+1; } else { prob*=(n-k); prob/=n; prob*=b+1; prob/=b-ct+1; } //cout << ct << " " << b <<" " << k <<" " <<n <<" " << prob << endl; if (prob<1e-7) { return -1; } ct+=bol; b++; } return ct; } signed main() { /*#ifndef ONLINE_JUDGE // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); #endif*/ rng.discard(time(NULL)%1000); ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; vector<string> ar(n); vector<int> order(n); vector<int> sorder(m); vector<int> visited(n,0); for (int i=0; i<n; i++) { int r = (rng())%n; while (visited[r]) { r = rng()%n; r+=rng(); r%=n; } visited[r] = 1; order[i] = r; //assert(order[i]<n); //cout << i <<" " <<r << endl; } visited=vector<int>(m,0); for (int i=0; i<m; i++) { int r = (rng())%m; while (visited[r]) { r = rng()%m; r+=rng(); r%=m; } visited[r] = 1; sorder[i] = r; sorder[i] = i; //assert(order[i]<n); //cout << i <<" " <<r << endl; } for (int i=0; i<n; i++) { string s; cin >> s; vector<char> t(m); for (int j=0; j<m; j++) t[j] = s[sorder[j]]; string r; for (auto j:t) r.push_back(j); ar[i] = r; } for (int i=0; i<n; i++) { int gg = 1; for (int j=0; j<n; j++) { if (order[i]==order[j]) continue; //assert(ar[order[j]].size()==m); if (match(ar[order[i]],ar[order[j]])!=k) { gg=0; break; } } if (gg) { cout << order[i]+1 << endl; break; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...