Submission #1212316

#TimeUsernameProblemLanguageResultExecution timeMemory
1212316StefanSebezGenetics (BOI18_genetics)C++20
27 / 100
2093 ms23732 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 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; } int main(){ scanf("%i%i%i",&n,&m,&K); for(int i=0;i<n;i++) cin>>s[i]; 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; } } for(int i=0;i<n;i++){ if(was[i]) continue; for(int j=0;j<n;j++){ if(i==j) continue; 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:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     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...