Submission #793781

#	Time	Username	Problem	Language	Result	Execution time	Memory
793781		finn__	Mutating DNA (IOI21_dna)	C++17	0 / 100	32 ms	4848 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct fenwick_tree
{
    vector<T> t;

    fenwick_tree() {}

    fenwick_tree(size_t n) { t.resize(n); }

    void update(size_t i, T x)
    {
        ++i;
        while (i <= t.size())
            t[i - 1] += x, i += i & -i;
    }

    T range_sum(size_t i, size_t j)
    {
        T x = 0;
        ++j;
        while (j)
            x += t[j - 1], j -= j & -j;
        while (i)
            x += t[i - 1], i -= i & -i;
        return x;
    }
};

constexpr size_t N = 100000;

string a, b;
fenwick_tree<int> at[3], bt[3];
bitset<N> matched;

void init(string a_, string b_)
{
    a = a_;
    b = b_;
    for (size_t i = 0; i < 3; ++i)
        at[i] = fenwick_tree<int>(a.size()), bt[i] = fenwick_tree<int>(b.size());
    for (size_t i = 0; i < a.size(); ++i)
    {
        if (a[i] == 'A')
            at[0].update(i, 1);
        else if (a[i] == 'C')
            at[1].update(i, 1);
        else
            at[2].update(i, 1);

        if (b[i] == 'A')
            bt[0].update(i, 1);
        else if (b[i] == 'C')
            bt[1].update(i, 1);
        else
            bt[2].update(i, 1);
    }
}

bool equal_set_in_range(size_t i, size_t j)
{
    return at[0].range_sum(i, j) == bt[0].range_sum(i, j) &&
           at[1].range_sum(i, j) == bt[1].range_sum(i, j) &&
           at[2].range_sum(i, j) == bt[2].range_sum(i, j);
}

int get_distance(int x, int y)
{
    if (!equal_set_in_range(x, y))
        return -1;

    int ans = 0, num_matched = 0;
    for (int i = x; i <= y; ++i)
    {
        if (!matched[i])
        {
            for (int j = i + 1; j <= y; ++j)
            {
                if (a[i] == b[j] && a[j] == b[i])
                {
                    num_matched += 2;
                    ans++;
                    matched[i] = 1;
                    matched[j] = 1;
                    break;
                }
            }
        }
    }

    for (int i = x; i <= y; ++i)
        matched[i] = 0;
    return ans + ((y - x + 1 - num_matched) / 3) * 2;
}

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