| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 917112 | pan | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 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_ioi.h"
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <string>
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
map<pi, ll> hashing;
vector<ll> one, two;
vector<vector<ll> >single, duo;
void init(string a, string b)
{
one.resize(a.length()); two.resize(a.length()); single.assign(a.length()+1, vector<ll> (3, 0)); duo.assign(a.length()+1, vector<ll> (6, 0));
hashing[mp(0,1)] = 0;
hashing[mp(0,2)] = 1;
hashing[mp(1,2)] = 2;
hashing[mp(2,1)] = 3;
hashing[mp(2,0)] = 4;
hashing[mp(1,0)] = 5;
for (ll i=0; i<a.length(); ++i)
{
if (a[i]=='A') one[i] = 0;
if (a[i]=='C') one[i] = 1;
if (a[i]=='T') one[i] = 2;
if (b[i]=='A') two[i] = 0;
if (b[i]=='C') two[i] = 1;
if (b[i]=='T') two[i] = 2;
for (ll j=0; j<3; ++j) single[i+1][j] = single[i][j];
single[i+1][one[i]]++;
single[i+1][two[i]]--;
for (ll j=0; j<6; ++j) duo[i+1][j] = duo[i][j];
duo[i+1][hashing[mp(one[i], two[i])]]++;
}
}
int get_distance(int x, int y)
{
y++;
for (ll i=0; i<3; ++i)
{
if (single[y][i] - single[x][i]!=0) return -1;
}
ll ans = 0;
ll tem1 = duo[y][hashing[mp(0,1)]] - duo[x][hashing[mp(0,1)]];
ll tem2 = duo[y][hashing[mp(1,0)]] - duo[x][hashing[mp(1,0)]];
ans+=min(tem1, tem2);
tem1-=min(tem1, tem2);
tem2-=min(tem1, tem2);
ans += 2*max(tem1, tem2);
tem1 = duo[y][hashing[mp(1,2)]]-duo[x][hashing[mp(1,2)]];
tem2 = duo[y][hashing[mp(2,1)]]-duo[x][hashing[mp(2,1)]];
ans+=min(tem1, tem2);
tem1-=min(tem1, tem2);
tem2-=min(tem1, tem2);
tem1 = duo[y][hashing[mp(0,2)]]-duo[x][hashing[mp(0,2)]];
tem2 = duo[y][hashing[mp(2,0)]]-duo[x][hashing[mp(2,0)]];
ans+=min(tem1, tem2);
tem1-=min(tem1, tem2);
tem2-=min(tem1, tem2);
return ans;
}