Submission #1167958

#TimeUsernameProblemLanguageResultExecution timeMemory
1167958razivoGenetics (BOI18_genetics)C++20
46 / 100
2091 ms25580 KiB
#include <iostream> #include <set> #include <vector> #include <bitset> #include <string> #include <unordered_set> #include <algorithm> #include <unordered_set> using namespace std; vector<string> a;int N,M,K; vector<bitset<4100>> l1; vector<bitset<4100>> l2; vector<bitset<4100>> c(4100); vector<bitset<4100>> t(4100); bool comp(int i, int j) { if(i>j) swap(i,j); if(c[i][j]) return t[i][j]; bool u = ((l1[i]^l1[j]) | (l2[i]^l2[j])).count() == K; c[i][j]=true; t[i][j] = u; return u; } int main() { cin>>N>>M>>K; l1.resize(N); l2.resize(N); for (int i = 0; i < N; ++i) { string s; cin>>s; a.push_back(s); for (int j = 0; j < M; ++j) { l1[i][j]= (s[j]=='A' || s[j]=='C'); l2[i][j]= (s[j]=='A' || s[j]=='G'); } } unordered_set<int> s; vector<int> com; for (int i = 0; i < N; ++i) { s.insert(i); } while(!s.empty()) { int u = *s.begin(); for(int v :s) { if(v==u) continue; if(!comp(u,v)) { com.push_back(v); com.push_back(u); s.erase(v); s.erase(u); goto label1; } } for(int v :com) { if(v==u) continue; if(!comp(u,v)) { com.push_back(u); s.erase(u); goto label1; } } cout<<(u+1)<<endl; exit(0); label1: int t =1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...