Submission #437136

#	Time	Username	Problem	Language	Result	Execution time	Memory
437136		illyakr	Mutating DNA (IOI21_dna)	C++17	100 / 100	140 ms	11344 KiB

dna

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

struct Info {
    int AonT, AonC;
    int TonA, TonC;
    int ConA, ConT;
    // A, T, C;
};
int n;
Info t[401010];
string A, B;
void build(int v, int vl, int vr) {
    if (vl == vr) {
        if (A[vl] == B[vl])return;
        if (A[vl] == 'A' && B[vl] == 'T')t[v].AonT = 1;
        if (A[vl] == 'A' && B[vl] == 'C')t[v].AonC = 1;

        if (A[vl] == 'T' && B[vl] == 'A')t[v].TonA = 1;
        if (A[vl] == 'T' && B[vl] == 'C')t[v].TonC = 1;

        if (A[vl] == 'C' && B[vl] == 'A')t[v].ConA = 1;
        if (A[vl] == 'C' && B[vl] == 'T')t[v].ConT = 1;

        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);

    t[v].AonT = t[2 * v].AonT + t[2 * v + 1].AonT;
    t[v].AonC = t[2 * v].AonC + t[2 * v + 1].AonC;

    t[v].TonA = t[2 * v].TonA + t[2 * v + 1].TonA;
    t[v].TonC = t[2 * v].TonC + t[2 * v + 1].TonC;

    t[v].ConA = t[2 * v].ConA + t[2 * v + 1].ConA;
    t[v].ConT = t[2 * v].ConT + t[2 * v + 1].ConT;

    return;
}
Info gt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)return t[v];
    if (r < vl || vr < l)return {0, 0, 0, 0, 0, 0};
    int vm = (vl + vr) / 2;
    auto f = gt(2 * v, vl, vm, l, r);
    auto s = gt(2 * v + 1, vm + 1, vr, l, r);
    return {f.AonT + s.AonT, f.AonC + s.AonC,
            f.TonA + s.TonA, f.TonC + s.TonC,
            f.ConA + s.ConA, f.ConT + s.ConT};
}

int acntA[101010], acntT[101010], acntC[101010];
int bcntA[101010], bcntT[101010], bcntC[101010];
void init(std::string a, std::string b) {
    n = a.size();
    A = a; B = b;
    build(1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            acntA[i] = acntA[i - 1];
            acntT[i] = acntT[i - 1];
            acntC[i] = acntC[i - 1];

            bcntA[i] = bcntA[i - 1];
            bcntT[i] = bcntT[i - 1];
            bcntC[i] = bcntC[i - 1];
        }
        if (a[i] == 'A')acntA[i]++;
        if (a[i] == 'T')acntT[i]++;
        if (a[i] == 'C')acntC[i]++;

        if (b[i] == 'A')bcntA[i]++;
        if (b[i] == 'T')bcntT[i]++;
        if (b[i] == 'C')bcntC[i]++;
    }
}

int get_distance(int x, int y) {
    int aA = acntA[y], aT = acntT[y], aC = acntC[y];
    if (x > 0){aA -= acntA[x - 1]; aT -= acntT[x - 1]; aC -= acntC[x - 1];}
    int bA = bcntA[y], bT = bcntT[y], bC = bcntC[y];
    if (x > 0){bA -= bcntA[x - 1]; bT -= bcntT[x - 1]; bC -= bcntC[x - 1];}
    if (aA != bA || aT != bT || aC != bC)return -1;

    auto have = gt(1, 0, n - 1, x, y);
    int ans = 0;
    {
        int M = min(have.AonT, have.TonA);
        have.AonT -= M;
        have.TonA -= M;
        ans += M;
    }
    {
        int M = min(have.AonC, have.ConA);
        have.AonC -= M;
        have.ConA -= M;
        ans += M;
    }
    {
        int M = min(have.TonC, have.ConT);
        have.TonC -= M;
        have.ConT -= M;
        ans += M;
    }
    int F = max(have.AonT, have.TonA);
    int S = max(have.AonC, have.ConA);
    int T = max(have.TonC, have.ConT);
    ans += (max({F, S, T}) + max({min(F, S), min(S, T), min(F, T)}));

/*
struct Info {
    int AonT, AonC;
    int TonA, TonC;
    int ConA, ConT;
    // A, T, C;
};
*/
    return ans;
}

/**
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

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