제출 #793791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793791		finn__	DNA 돌연변이 (IOI21_dna)	C++17	21 / 100	45 ms	4808 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(int64_t i, T x)
    {
        ++i;
        while (i <= t.size())
            t[i - 1] += x, i += i & -i;
    }

    T range_sum(int64_t i, int64_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])
        {
            if (a[i] == b[i])
                matched[i] = 1, num_matched++;
            else
            {
                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;
}

컴파일 시 표준 에러 (stderr) 메시지

dna.cpp: In instantiation of 'void fenwick_tree<T>::update(int64_t, T) [with T = int; int64_t = long int]':
dna.cpp:48:30:   required from here
dna.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~

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