#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const string kDna = "ATC";
const int K = kDna.size();
vector<int> prefix_sum[sizeof(char) << 8][sizeof(char) << 8];
int cnt[sizeof(char) << 8][sizeof(char) << 8];
vector<string> dna_subsets;
constexpr int kImpossible = -1;
void init(string A, string B) {
int N = A.size();
for (int c1 : kDna) {
for (int c2 : kDna) {
prefix_sum[c1][c2].resize(N);
}
}
for (int c1 : kDna) {
for (int c2 : kDna) {
for (int i = 0; i < N; ++i) {
prefix_sum[c1][c2][i] = (c1 == A[i] && c2 == B[i]) ? 1 : 0;
if (i > 0) {
prefix_sum[c1][c2][i] += prefix_sum[c1][c2][i - 1];
}
}
}
}
for (int bit = 1; bit < (1 << K); ++bit) {
string dna_subset;
for (int i = 0; i < K; ++i) {
if (bit & (1 << i)) {
dna_subset += kDna[i];
}
}
dna_subsets.push_back(dna_subset);
}
sort(dna_subsets.begin(), dna_subsets.end(), [] (string a, string b) {
return a.size() < b.size();
});
}
int get_distance(int X, int Y) {
for (int c1 : kDna) {
for (int c2 : kDna) {
cnt[c1][c2] = prefix_sum[c1][c2][Y];
if (X > 0) {
cnt[c1][c2] -= prefix_sum[c1][c2][X - 1];
}
}
}
int answer = Y - X + 1;
for (string dna_subset : dna_subsets) {
for (int tries = 0; tries < 2; ++tries) {
int res = INT_MAX;
for (int i = 0; i < static_cast<int>(dna_subset.size()); ++i) {
int c1 = dna_subset[i];
int c2 = dna_subset[(i + 1) % dna_subset.size()];
res = min(res, cnt[c1][c2]);
}
answer -= res;
for (int i = 0; i < static_cast<int>(dna_subset.size()); ++i) {
int c1 = dna_subset[i];
int c2 = dna_subset[(i + 1) % dna_subset.size()];
cnt[c1][c2] -= res;
}
}
}
for (int c1 : kDna) {
for (int c2 : kDna) {
if (cnt[c1][c2] > 0) {
return kImpossible;
}
}
}
return answer;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
7156 KB |
Output is correct |
2 |
Correct |
93 ms |
7248 KB |
Output is correct |
3 |
Incorrect |
90 ms |
6888 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
10 ms |
5836 KB |
Output is correct |
5 |
Correct |
11 ms |
5968 KB |
Output is correct |
6 |
Correct |
11 ms |
5836 KB |
Output is correct |
7 |
Correct |
11 ms |
5580 KB |
Output is correct |
8 |
Correct |
10 ms |
5976 KB |
Output is correct |
9 |
Correct |
8 ms |
5976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
10 ms |
5836 KB |
Output is correct |
5 |
Correct |
11 ms |
5968 KB |
Output is correct |
6 |
Correct |
11 ms |
5836 KB |
Output is correct |
7 |
Correct |
11 ms |
5580 KB |
Output is correct |
8 |
Correct |
10 ms |
5976 KB |
Output is correct |
9 |
Correct |
8 ms |
5976 KB |
Output is correct |
10 |
Correct |
97 ms |
7160 KB |
Output is correct |
11 |
Correct |
105 ms |
7180 KB |
Output is correct |
12 |
Correct |
93 ms |
7284 KB |
Output is correct |
13 |
Correct |
86 ms |
7412 KB |
Output is correct |
14 |
Correct |
90 ms |
7560 KB |
Output is correct |
15 |
Correct |
96 ms |
7460 KB |
Output is correct |
16 |
Correct |
83 ms |
7272 KB |
Output is correct |
17 |
Correct |
82 ms |
7436 KB |
Output is correct |
18 |
Correct |
91 ms |
7536 KB |
Output is correct |
19 |
Correct |
83 ms |
7272 KB |
Output is correct |
20 |
Correct |
86 ms |
7432 KB |
Output is correct |
21 |
Correct |
80 ms |
7672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1740 KB |
Output is correct |
2 |
Correct |
2 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
10 ms |
5836 KB |
Output is correct |
5 |
Correct |
11 ms |
5968 KB |
Output is correct |
6 |
Correct |
11 ms |
5836 KB |
Output is correct |
7 |
Correct |
11 ms |
5580 KB |
Output is correct |
8 |
Correct |
10 ms |
5976 KB |
Output is correct |
9 |
Correct |
8 ms |
5976 KB |
Output is correct |
10 |
Incorrect |
10 ms |
5628 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
7156 KB |
Output is correct |
2 |
Correct |
93 ms |
7248 KB |
Output is correct |
3 |
Incorrect |
90 ms |
6888 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |