| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1274699 | Davdav1232 | Genetics (BOI18_genetics) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx,avx2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vii;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k; cin>>n>>m>>k;
vector<pair<string, int>> villains(n);
for(int i=0; i<n; i++){
cin>>villains[i].first;
villains[i].second=i+1;
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(villains[i].first[j]=='A') villains[i].first[j]-='A';
if(villains[i].first[j]=='C') villains[i].first[j]-='C'-1;
if(villains[i].first[j]=='G') villains[i].first[j]-='G'-2;
if(villains[i].first[j]=='T') villains[i].first[j]-='T'-3;
}
}
vector<bool> is_real(n, 1);
int rounds=30;
random_device g;
while(rounds--){
vector<vector<int>> count(m, vector<int> (4, 0));
shuffle(villains.begin(), villains.end(), g);
for(int i=0; i<n; i++){
int curr=i*k;
for(int j=0; j<m; j++){
curr-=i-count[j][villains[i].first[j]];
count[j][villains[i].first[j]]++;
}
if(curr!=0){
is_real[villains[i].second-1]=0;
}
}
}
for(int i=0; i<n; i++){
if(is_real[i]){
cout<<i+1;
return 0;
}
}
return 0;
}