oj.uz

Submission #393055

# Submission time Handle Problem Language Result Execution time Memory
393055 2021-04-22T15:47:23 Z ollel Genetics (BOI18_genetics) C++14
27 / 100
 2000 ms 10572 KB 
#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;

  }

}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 3 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 8 ms 296 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 10572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 10572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 3 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 8 ms 296 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 2096 ms 10572 KB Time limit exceeded
19 Halted 0 ms 0 KB -