Submission #784120

#	Time	Username	Problem	Language	Result	Execution time	Memory
784120		AC2K	Mutating DNA (IOI21_dna)	C++17	56 / 100	36 ms	6384 KiB

dna

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

using namespace std;

namespace imple {

string a, b;
int n;
vector<int> diff;
vector<array<int, 3>> Ca, Cb;
const string DNA = "ATC";

void init(string _a, string _b) {
    a = _a, b = _b;

    diff.resize(a.size() + 1), Ca.resize(b.size() + 1), Cb.resize(b.size() + 1);

    for (int i = 0; i < (int)a.size(); ++i) {
        diff[i + 1] = diff[i] + (a[i] != b[i]);
    }

    for (int i = 0; i < (int)a.size(); ++i) {
        Ca[i + 1] = Ca[i];
        ++Ca[i + 1][DNA.find(a[i])];
    }

    for (int i = 0; i < (int)b.size(); ++i) {
        Cb[i + 1] = Cb[i];
        ++Cb[i + 1][DNA.find(b[i])];
    }
}

int query(int l, int r) {
    for (int i = 0; i < 3; ++i) {
        if (Ca[r + 1][i] - Ca[l][i] != Cb[r + 1][i] - Cb[l][i]) {
            return -1;
        }
    }

    return (diff[r + 1] - diff[l] + 1) / 2;
}

};  // namespace imple

void init(string a, string b) { imple::init(a, b); }

int get_distance(int x, int y) { return imple::query(x, y); }

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