Submission #738689

#	Time	Username	Problem	Language	Result	Execution time	Memory
738689		aykhn	Mutating DNA (IOI21_dna)	C++17	100 / 100	108 ms	10316 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

// author: aykhn

using namespace std;

typedef long long ll;

const int oo = INT_MAX;
const ll ooo = LONG_MAX;
const ll mod = 1e9 + 7;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0);
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

struct cus
{
    int AC = 0;
    int AT = 0;
    int CA = 0;
    int CT = 0;
    int TA = 0;
    int TC = 0;
};

int sz = 1;
vector<cus> tree;

string a, b;

cus MERGE(cus one, cus two)
{
    cus res;

    res.AT = one.AT + two.AT;
    res.AC = one.AC + two.AC;
    res.CA = one.CA + two.CA;
    res.CT = one.CT + two.CT;
    res.TA = one.TA + two.TA;
    res.TC = one.TC + two.TC;

    return res;
}

void build(int l, int r, int x)
{
    if (l + 1 == r)
    {
        if (l < a.length() && a[l] != b[l])
        {
            if (a[l] == 'A' && b[l] == 'C') tree[x].AC++;
            else if (a[l] == 'A' && b[l] == 'T') tree[x].AT++;
            else if (a[l] == 'C' && b[l] == 'A') tree[x].CA++;
            else if (a[l] == 'C' && b[l] == 'T') tree[x].CT++;
            else if (a[l] == 'T' && b[l] == 'A') tree[x].TA++;
            else if (a[l] == 'T' && b[l] == 'C') tree[x].TC++;
        }

        return;
    }

    int mid = (l + r) >> 1;

    build(l, mid, 2*x+1);
    build(mid, r, 2*x+2);

    tree[x] = MERGE(tree[2*x+1], tree[2*x+2]);
}

cus get(int lx, int rx, int l, int r, int x)
{
    if (l >= rx || r <= lx)
    {
        cus temp;
        return temp;
    }

    if (l >= lx && r <= rx) return tree[x];

    int mid = (l + r) >> 1;

    return MERGE(get(lx, rx, l, mid, 2*x+1), get(lx, rx, mid, r, 2*x+2));
}



void init(string s1, string s2)
{
    a = s1;
    b = s2;

    int n = s1.length();

    while (sz < n) sz <<= 1;
    cus temp;
    temp.AC = temp.AT = temp.CA = temp.CT = temp.TA = temp.TC = 0;

    tree.assign(sz * 2, temp);

    build(0, sz, 0);
}

int get_distance(int l, int r)
{
    cus x = get(l, r + 1, 0, sz, 0);

    if (x.AT + x.AC != x.TA + x.CA || x.CA + x.CT != x.AC + x.TC || x.TA + x.TC != x.AT + x.CT) return -1;

    //cout << "AC: " << x.AC << endl << "AT: " << x.AT << endl << "CA: " << x.CA << endl << "CT: " << x.CT << endl << "TA: " << x.TA << endl << "TC: " << x.TC << endl << endl;

    int res = 0;

    int temp = min(x.AT, x.TA);

    res += temp;
    x.AT -= temp;
    x.TA -= temp;

    temp = min(x.AC, x.CA);

    res += temp;
    x.AC -= temp;
    x.CA -= temp;

    temp = min(x.CT, x.TC);

    res += temp;
    x.CT -= temp;
    x.TC -= temp;

    temp = min({x.AC, x.CT, x.TA});

    res += temp*2;

    x.AC -= temp;
    x.CT -= temp;
    x.TA -= temp;

    temp = min({x.AT, x.TC, x.CA});

    res += temp*2;

    return res;
}

Compilation message (stderr)

dna.cpp: In function 'void build(int, int, int)':
dna.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if (l < a.length() && a[l] != b[l])
      |             ~~^~~~~~~~~~~~

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