Submission #574750

#	Time	Username	Problem	Language	Result	Execution time	Memory
574750		four_specks	Mutating DNA (IOI21_dna)	C++17	56 / 100	35 ms	6676 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

inline namespace tc
{
} // namespace tc

namespace
{
    array<vector<int>, 3> pref_a, pref_b;
    vector<int> diff;

} // namespace

const map<char, int> mp = {{pair('A', 0), pair('T', 1), pair('C', 2)}};

void init(string a, string b)
{
    int n = (int)a.length();
    pref_a.fill(vector<int>(n + 1, 0)), pref_b.fill(vector<int>(n + 1, 0));
    diff = vector<int>(n + 1, 0);
    for (int i = 0; i < n; i++)
    {
        for (int c = 0; c < 3; c++)
            pref_a[c][i + 1] = pref_a[c][i], pref_b[c][i + 1] = pref_b[c][i];
        pref_a[mp.at(a[i])][i + 1]++, pref_b[mp.at(b[i])][i + 1]++;
        diff[i + 1] = diff[i] + (a[i] != b[i]);
    }
}

int get_distance(int x, int y)
{
    ++y;

    bool ok = 1;
    for (int c = 0; c < 3; c++)
        ok &= pref_a[c][y] - pref_a[c][x] == pref_b[c][y] - pref_b[c][x];

    if (ok)
        return (diff[y] - diff[x] + 1) / 2;
    return -1;
}

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