제출 #1215496

#제출 시각아이디문제언어결과실행 시간메모리
1215496boclobanchatGenetics (BOI18_genetics)C++20
46 / 100
2093 ms18504 KiB
#include<bits/stdc++.h> using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l,int r) { return uniform_int_distribution<int>(l,r)(rng); } const int MAXN=4114; bitset<MAXN> bt[MAXN][2]; bool ck[MAXN],cs[MAXN][MAXN]; int vi[MAXN]; int get(int x,int y) { return ((bt[x][0]^bt[y][0])|(bt[x][1]^bt[y][1])).count(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,k; cin>>n>>m>>k; int cnt=n; for(int i=1;i<=n;i++) { string s; cin>>s; for(int j=0;j<m;j++) { if(s[j]=='A'||s[j]=='C') bt[i][0][j]=1; if(s[j]=='A'||s[j]=='G') bt[i][1][j]=1; } } for(int i=1;i<=n;i++) cs[i][i]=true,vi[i]=i; while(cnt>1) { int pcnt=cnt; int l=Rand(1,cnt),r=Rand(1,n); while(cs[vi[l]][r]) l=Rand(1,cnt),r=Rand(1,n); l=vi[l]; cs[l][r]=cs[r][l]=true; if(get(l,r)!=k) { if(!ck[l]) ck[l]=true,cnt--; if(!ck[r]) ck[r]=true,cnt--; } if(pcnt!=cnt) { cnt=0; for(int j=1;j<=n;j++) if(!ck[j]) vi[++cnt]=j; } } for(int i=1;i<=n;i++) if(!ck[i]) return cout<<i,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...