Submission #1053608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053608		damjandavkov	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	7772 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n, i, j, k;
vector<vector<int> > pf(9, {0});
vector<int> cv = {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0}, o(9);
void init(string a, string b)
{
    n = a.size();
    for (i = 0; i < n; i++)
    {
        j = cv[a[i] - 65] * 3 + cv[b[i] - 65];
        for (k = 0; k < 9; k++)
            pf[k].push_back(pf[k].back() + (k == j));
    }
}
void ch(vector<int> q)
{
    j = n;
    for (auto h : q)
        j = min(j, o[h]);
    k += j;
    for (auto h : q)
        o[h] -= j;
}
int get_distance(int x, int y)
{
    y++;
    k = 0;
    for (i = 0; i < 9; i++)
        o[i] = pf[i][y] - pf[i][x];
    ch({0});
    ch({4});
    ch({8});
    ch({1, 3});
    ch({5, 7});
    ch({6, 2});
    ch({1, 5, 6});
    ch({3, 7, 2});
    for (i = 0; i < 9; i++)
    {
        if (o[i])
            return -1;
    }
	return y - x - k;
}

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