Submission #756546

#	Time	Username	Problem	Language	Result	Execution time	Memory
756546		caganyanmaz	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	6252 KiB

dna

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

struct Fenwick
{
        int n;
        vector<int> data;
        Fenwick(int n) : n(n), data(n + 1) {}
        Fenwick() : Fenwick(0) {}
        void update(int i, int val) { for (++i;i<data.size();i+=i&(-i)) data[i] += val; }
        int get(int i) { int res=0; for (;i;i-=i&(-i)) res += data[i]; return res; }
        int get(int l, int r) { return get(r) - get(l); }
};

Fenwick d[3][3];
int v[3][3];

int cc(char c)
{
        switch (c)
        {
                case 'A':
                        return 0;
                case 'T':
                        return 1;
                case 'C':
                        return 2;
                default:
                        assert(false);
        }
}

void init(string a, string b)
{
        int n = a.size();
        for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                        if (i != j)
                                d[i][j] = Fenwick(n);
        for (int i = 0; i < n; i++)
        {
                int x = cc(a[i]), y = cc(b[i]);
                if (x != y)
                        d[x][y].update(i, 1);
        }
}

bool check(int x)
{
        int sum = 0;
        for (int i = 0; i < 3; i++)
                sum += v[i][x] - v[x][i];
        return !sum;
}


int get_distance(int l, int r)
{
        r++;
        for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                        v[i][j] = (i == j) ? 0 : d[i][j].get(l, r);
        //for (int i = 0; i < 3; i++)
        //{
        //      for (int j = 0; j < 3; j++)
        //              cout << v[i][j] << " ";
        //      cout << "\n";
        //}
        if (check(0) && check(1) && check(2))
        {
                return
                        min(v[0][1], v[1][0]) +
                        min(v[0][2], v[2][0]) +
                        min(v[1][2], v[2][1]) +
                        2 * (v[0][1] + v[1][0] - 2 * min(v[0][1], v[1][0]));
        }
        else
                return -1;

}

Compilation message (stderr)

dna.cpp: In member function 'void Fenwick::update(int, int)':
dna.cpp:10:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         void update(int i, int val) { for (++i;i<data.size();i+=i&(-i)) data[i] += val; }
      |                                                ~^~~~~~~~~~~~

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