제출 #393054

#제출 시각아이디문제언어결과실행 시간메모리
393054ollelGenetics (BOI18_genetics)C++14
0 / 100
2071 ms13120 KiB
#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define LSO(x) x&(-x)

typedef vector<int> vi;
typedef long long ll;

int n, k, m;

map<char, int> charmap;


void convert(string inp, vi& ret) {
  int n = inp.size();
  rep(i,0,n) ret[i] = charmap[inp[i]];
}

bool compare(vi& g1, vi& g2) {
  int difs = 0;
  rep(i,0,m) if (g1[i] != g2[i]) difs++;
  return (difs <= k);
}

int main()
{
  charmap.insert(pair<char, int>('A', 0));
  charmap.insert(pair<char, int>('T', 1));
  charmap.insert(pair<char, int>('C', 2));
  charmap.insert(pair<char, int>('G', 3));
  cin >>n>>m>>k;
  vector<vi> genes(n, vi(m));
  string inp;
  rep(i,0,n) {
    cin >> inp;
    convert(inp, genes[i]);
  }

  rep(i,0,n) {
    int score = 0;
    rep(j, 0, n) {
      if (j != i) {
        if (!compare(genes[i], genes[j])) score++;
      }
    }
    if (!score) cout << i + 1 << endl;

  }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...