Submission #1129025

#TimeUsernameProblemLanguageResultExecution timeMemory
1129025LudisseyGenetics (BOI18_genetics)C++20
19 / 100
2108 ms306556 KiB
#include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m,k; cin >> n >> m >> k; int blocks=(m/64)+1; vector<vector<int>> a_c(n,vector<int>(blocks+1)); vector<vector<int>> g_t(n,vector<int>(blocks+1)); for (int i = 0; i < n; i++) { int j=0; int bl=0; while(j<m){ char c; cin >> c; if(c=='A') a_c[i][bl]+=(1LL<<j); if(c=='T') g_t[i][bl]+=(1LL<<j); j++; if(j%64==0) bl++; } } vector<vector<int>> dist(n,vector<int>(n,0)); vector<vector<int>> dist2(n,vector<int>(n,0)); vector<vector<int>> dist3(n,vector<int>(n,0)); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { for (int _k = 0; _k < blocks; _k++) { dist[i][j]+=__builtin_popcountll(a_c[i][_k]^a_c[j][_k]); dist2[i][j]+=__builtin_popcountll(g_t[i][_k]^g_t[j][_k]); dist3[i][j]+=__builtin_popcountll(g_t[i][_k]&a_c[j][_k]); dist3[i][j]+=__builtin_popcountll(a_c[i][_k]&g_t[j][_k]); } dist[j][i]=dist[i][j]; dist2[j][i]=dist2[i][j]; dist3[j][i]=dist3[i][j]; } } for (int i = 0; i < n; i++) { bool b=true; for (int j = 0; j < n; j++) { if(i==j) continue; if((dist[i][j]+dist2[i][j])-dist3[i][j]!=k) { b=false; break; } } if(b==true){ cout << i+1 << "\n"; break; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...