Submission #393284

#	Time	Username	Problem	Language	Result	Execution time	Memory
393284		ollel	Genetics (BOI18_genetics)	C++14	27 / 100	2085 ms	10572 KiB

genetics

#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]);
  }

  vector<bool> no(n,false);

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

  }

}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26