# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
548524 | Clan328 | Mutating DNA (IOI21_dna) | C++17 | 140 ms | 38604 KiB |
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 "dna.h"
#include <bits/stdc++.h>
using namespace std;
string a, b;
vector<int> diff;
vector<map<char, int>> dp1, dp2;
void init(std::string A, std::string B) {
a = A;
b = B;
diff = vector<int>(a.size());
dp1 = vector<map<char, int>>(a.size());
dp2 = vector<map<char, int>>(a.size());
for (int i = 0; i < a.size(); i++) {
diff[i] = i+1 - (a[i] == b[i]);
if (i > 0) {
dp1[i] = dp1[i-1];
dp2[i] = dp2[i-1];
}
dp1[i][a[i]]++;
dp2[i][b[i]]++;
}
}
int get_distance(int x, int y) {
if (x != 0) {
if (!(
dp1[y]['A']-dp1[x-1]['A'] == dp2[y]['A']-dp2[x-1]['A'] &&
dp1[y]['C']-dp1[x-1]['C'] == dp2[y]['C']-dp2[x-1]['C'] &&
dp1[y]['T']-dp1[x-1]['T'] == dp2[y]['T']-dp2[x-1]['T']
))
return -1;
} else {
if (!(
dp1[y]['A'] == dp2[y]['A'] &&
dp1[y]['C'] == dp2[y]['C'] &&
dp1[y]['T'] == dp2[y]['T']
)) return -1;
}
if (x != 0)
return (diff[y]-diff[x-1]+1)/2;
else
return (diff[y]+1)/2;
}
Compilation message (stderr)
# | 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... |