Submission #1212317

#TimeUsernameProblemLanguageResultExecution timeMemory
1212317StefanSebezGenetics (BOI18_genetics)C++20
46 / 100
2058 ms31180 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double #pragma GCC target("popcnt") const int N=4110; mt19937 rng(time(0)); int n,m,K; string s[N]; bool was[N]; int dist[N][N]; int Get(int i,int j){ if(dist[i][j]) return dist[i][j]; int res=0; for(int k=0;k<m;k++) if(s[i][k]!=s[j][k]) res++; return dist[i][j]=res; } bitset<N>bt[4][N]; int GET(int i,int j){ int res=0; for(int k=0;k<4;k++){ res+=(bt[k][i]&bt[k][j]).count(); } return m-res; } int main(){ scanf("%i%i%i",&n,&m,&K); for(int i=0;i<n;i++) cin>>s[i]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s[i][j]=='A') bt[0][i][j]=1; if(s[i][j]=='C') bt[1][i][j]=1; if(s[i][j]=='G') bt[2][i][j]=1; if(s[i][j]=='T') bt[3][i][j]=1; } } /*for(int ct=1;ct<=n;ct++){ vector<int>temp; for(int i=0;i<n;i++) temp.pb(i); shuffle(temp.begin(),temp.end(),rng); vector<int>ind; bool broke=false; for(auto i:temp){ if(!was[i]){ for(auto j:ind){ if(Get(i,j)!=K){ was[i]=was[j]=true; broke=true; } } ind.pb(i); } if(broke) break; } if(ind.size()==1) break; }*/ for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(GET(i,j)!=K) was[i]=was[j]=true; } } int res=0; for(int i=0;i<n;i++) if(!was[i]) res=i; res++; printf("%i\n",res); return 0; }

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%i%i%i",&n,&m,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...