| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1239403 | lunarecho | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> prefix1, prefix2, prefix3, prefix4, prefix5;
string c,d;
void init(std::string a, std::string b) {
c = a;
d = b;
int n = (int)c.size();
prefix1.resize(n+1,0);
prefix2.resize(n+1,0);
prefix3.resize(n+1,0);
prefix4.resize(n+1,0);
prefix5.resize(n+1,0);
for(int i=0;i<n;++i)
{
prefix1[i + 1] += prefix1[i];
prefix1[i + 1] += (c[i] == 'A');
prefix2[i + 1] += prefix2[i];
prefix2[i + 1] += (c[i] == 'T');
prefix3[i + 1] += prefix3[i];
prefix3[i + 1] += (d[i] == 'A');
prefix4[i + 1] += prefix4[i];
prefix4[i + 1] += (d[i] == 'T');
prefix5[i + 1] += prefix5[i];
prefix5[i + 1] += (c[i] != d[i]);
}
}
int get_distance(int x, int y) {
if(y - x <= 2)
{
if(y - x == 0)
{
return c[x] == d[x] ? 0 : -1;
}
else if(y - x == 1)
{
if(c[x] == d[x] && c[y] == d[y])
return 0;
if(c[x + 1] == d[x] && c[x] == d[x + 1])
return 1;
return -1;
}
else
{
int a1 = 0, b1 = 0, c1 = 0;
for(int i=x;i<y;++i)
{
a1 += (c[i] == 'A');
b1 += (c[i] == 'T');
a1 += (c[i] == 'C');
}
int d1 = 0, e1 = 0, f1 = 0;
for(int i=x;i<y;++i)
{
d1 += (d[i] == 'A');
e1 += (d[i] == 'T');
f1 += (d[i] == 'C');
}
if(a1 != d1 || b1 != e1 || c1 != f1)
return -1;
int diff = 0;
for(int i=x;i<y;++i)
if(c[i] != d[i])
++diff;
if(difff & 1)
return -1;
return diff / 2;
}
}
int difff = prefix5[y + 1] - prefix5[x];
if(difff & 1)
return -1;
int abc1 = prefix1[y + 1] - prefix1[x];
int abc2 = prefix2[y + 1] - prefix2[x];
int abc3 = prefix3[y + 1] - prefix3[x];
int abc4 = prefix4[y + 1] - prefix4[x];
if(abc1 != abc3 || abc2 != abc4)
return -1;
return difff / 2;
}