This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <string>
#include <iostream>
using namespace std;
const int maxN = 100005;
int n, v1[maxN], v2[maxN], sp[maxN][10], sp1[maxN][3], sp2[maxN][3];
int getCode(char c) {
if (c == 'A') {
return 0;
}
if (c == 'C') {
return 1;
}
if (c == 'T') {
return 2;
}
}
void initString(string s, int v[], int sp[maxN][3]) {
for (int i = 1; i <= n; i++) {
v[i] = getCode(s[i - 1]);
for (int j = 0; j < 3; j++) {
sp[i][j] = sp[i - 1][j];
}
sp[i][v[i]]++;
}
}
void init(string a, string b) {
n = (int) a.size();
initString(a, v1, sp1);
initString(b, v2, sp2);
for (int i = 1; i <= n; i++) {
int code = v1[i] * 3 + v2[i];
for (int j = 0; j < 9; j++) {
sp[i][j] = sp[i - 1][j];
}
sp[i][code]++;
}
}
/// AC = 1
/// AT = 2
/// CA = 3
/// CT = 5
/// TA = 6
/// TC = 7
int get_distance(int x, int y) {
y++;
for (int j = 0; j < 3; j++) {
if ((sp1[y][0] - sp1[x][0]) != (sp2[y][0] - sp2[x][0])) {
return -1;
}
}
int AC = sp[y][1] - sp[x][1];
int AT = sp[y][2] - sp[x][2];
int CA = sp[y][3] - sp[x][3];
int CT = sp[y][5] - sp[x][5];
int TA = sp[y][6] - sp[x][6];
int TC = sp[y][7] - sp[x][7];
int min1 = min(AC, CA), min2 = min(AT, TA), min3 = min(CT, TC);
int ans = min1 + min2 + min3;
AC -= min1, CA -= min1;
AT -= min2, TA -= min2;
CT -= min3, TC -= min3;
ans += 2 * (AC + CA);
return ans;
}
Compilation message (stderr)
dna.cpp: In function 'int getCode(char)':
dna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
19 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |