Submission #467486

#	Time	Username	Problem	Language	Result	Execution time	Memory
467486		alextodoran	Mutating DNA (IOI21_dna)	C++17	100 / 100	122 ms	23492 KiB

dna

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

typedef long long ll;

int encode (char c)
{
    if(c == 'A')
        return 0;
    if(c == 'C')
        return 1;
    if(c == 'T')
        return 2;

    assert(false);
}

vector <vector <vector <int>>> cntPref;

void init (string a, string b)
{
    int n = (int) a.size();
    cntPref = vector <vector <vector <int>>> (n, vector <vector <int>> (3, vector <int> (3)));

    for(int i = 0; i < n; i++)
    {
        if(i - 1 >= 0)
            cntPref[i] = cntPref[i - 1];
        cntPref[i][encode(a[i])][encode(b[i])]++;
    }
}

int get_distance (int x, int y)
{
    vector <vector <int>> cnt = cntPref[y];
    if(x - 1 >= 0)
    {
        for(int u = 0; u < 3; u++)
            for(int v = 0; v < 3; v++)
                cnt[u][v] -= cntPref[x - 1][u][v];
    }

    vector <int> cnta (3);
    vector <int> cntb (3);
    for(int u = 0; u < 3; u++)
        for(int v = 0; v < 3; v++)
        {
            cnta[u] += cnt[u][v];
            cntb[v] += cnt[u][v];
        }

    for(int u = 0; u < 3; u++)
        if(cnta[u] != cntb[u])
            return -1;

    int answer = 0;

    for(int u = 0; u < 3; u++)
        cnt[u][u] = 0;

    for(int u = 0; u < 3; u++)
        for(int v = u + 1; v < 3; v++)
        {
            int take = min(cnt[u][v], cnt[v][u]);
            answer += take;
            cnt[u][v] -= take;
            cnt[v][u] -= take;
        }

    int sum = 0;
    for(int u = 0; u < 3; u++)
        for(int v = 0; v < 3; v++)
            sum += cnt[u][v];
    answer += sum / 3 * 2;

    return answer;
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16