Submission #995756

#	Time	Username	Problem	Language	Result	Execution time	Memory
995756		asdasdqwer	Mutating DNA (IOI21_dna)	C++17	56 / 100	24 ms	6188 KiB

dna

#include "dna.h"

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

#define tii array<int,3>
vector<tii> cnt1, cnt2;
int n;

vector<int> dif;

int cnv(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    return 2;
}

tii operator-(const tii &x, const tii &y) {
    return {x[0]-y[0], x[1]-y[1], x[2]-y[2]};
}

void ii(string a, vector<tii> &cnt) {
    cnt[0][cnv(a[0])]++;
    for (int i=1;i<n;i++) {
        cnt[i] = cnt[i-1];
        cnt[i][cnv(a[i])]++;
    }
}

void init(string a, string b) {
    n = (int)a.size();
    cnt1.assign(n, {0, 0, 0});
    cnt2.assign(n, {0, 0, 0});

    ii(a, cnt1);
    ii(b, cnt2);

    dif.assign(n, 0);
    for (int i=0;i<n;i++) {
        if (a[i] != b[i]) dif[i]++;
    }

    for (int i=1;i<n;i++) {
        dif[i] += dif[i-1];
    }
}

int get_distance(int x, int y) {
    // first check count
    tii t1 = cnt1[y];
    if (x) {
        t1 = t1 - cnt1[x-1];
    }

    tii t2 = cnt2[y];
    if (x) {
        t2 = t2 - cnt2[x-1];
    }

    if (t1 != t2) {
        return -1;
    }

    int df = dif[y];
    if (x) {
        df -= dif[x-1];
    }

    df = (df/2) + (df%2);
    return df;
}

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