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;
int preff[100010][3][3];
int num[27];
void init(string a, string b) {
num['A'-'A']=0;
num['T'-'A']=1;
num['C'-'A']=2;
for(int i = 0; i < (int)a.size(); i++)
{
int x = num[a[i] - 'A'];
int y = num[b[i] - 'A'];
preff[i][x][y]++;
if(i != 0)
{
for(int x = 0; x < 3; x++)
{
for(int y = 0; y < 3; y++)
{
preff[i][x][y] += preff[i - 1][x][y];
}
}
}
}
}
int get_distance(int x, int y) {
int cnt[3][3];
memset(cnt,0,sizeof(cnt));
if(x == 0)
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
cnt[i][j]+=preff[y][i][j];
}
}
}
else
{
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
cnt[i][j]+=(preff[y][i][j]-preff[x-1][i][j]);
}
}
}
int ans=0;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
int cycle_2 = min(cnt[i][j],cnt[j][i]);
ans += cycle_2;
cnt[i][j] -= cycle_2;
cnt[j][i] -= cycle_2;
}
}
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 3; k++)
{
int cycle_3 = min(cnt[i][j],min(cnt[j][k],cnt[k][i]));
ans += cycle_3 * 2;
cnt[i][j] -= cycle_3;
cnt[j][k] -= cycle_3;
cnt[k][i] -= cycle_3;
}
}
}
return ans;
}
# | 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... |