Submission #442795

#	Time	Username	Problem	Language	Result	Execution time	Memory
442795		baluteshih	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	8196 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

int num[256];
int prea[3][100005], preb[3][100005];
int atdiff[100005], ac[100005], tc[100005], ca[100005], ct[100005];

int get_sum(int *arr, int l, int r) {
    if (l == 0)
        return arr[r];
    return arr[r] - arr[l - 1];
}

void init(string a, string b) {
    int n = SZ(a);
    num['A'] = 0, num['T'] = 1, num['C'] = 2;
    for (int i = 0; i < n; ++i) {
        ++prea[num[int(a[i])]][i];
        ++preb[num[int(b[i])]][i];
        atdiff[i] = (a[i] != b[i] && a[i] != 'C' && b[i] != 'C');
        ac[i] = (a[i] == 'A' && b[i] == 'C');
        tc[i] = (a[i] == 'T' && b[i] == 'C');
        ca[i] = (a[i] == 'C' && b[i] == 'A');
        ct[i] = (a[i] == 'C' && b[i] == 'T');
    }
    for (int i = 1; i < n; ++i) {
        prea[0][i] += prea[0][i - 1];
        prea[1][i] += prea[1][i - 1];
        prea[2][i] += prea[2][i - 1];
        preb[0][i] += preb[0][i - 1];
        preb[1][i] += preb[1][i - 1];
        preb[2][i] += preb[2][i - 1];
        atdiff[i] += atdiff[i - 1];
        ac[i] += ac[i - 1];
        tc[i] += tc[i - 1];
        ca[i] += ca[i - 1];
        ct[i] += ct[i - 1];
    }
}

int get_distance(int x, int y) {
    if (get_sum(prea[0], x, y) != get_sum(preb[0], x, y)) {
        return -1;
    }
    if (get_sum(prea[1], x, y) != get_sum(preb[1], x, y)) {
        return -1;
    }
    if (get_sum(prea[2], x, y) != get_sum(preb[2], x, y)) {
        return -1;
    }
	int cd = get_sum(ac, x, y) + get_sum(tc, x, y);
    int once = min(get_sum(ac, x, y), get_sum(ca, x, y)) + min(get_sum(tc, x, y), get_sum(ct, x, y));
    return cd + (cd - once + get_sum(atdiff, x, y)) / 2;
}

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