Submission #670491

#	Time	Username	Problem	Language	Result	Execution time	Memory
670491		Desh03	Mutating DNA (IOI21_dna)	C++17	56 / 100	35 ms	6924 KiB

dna

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

vector<int> v, a1, a2, c1, c2, t1, t2, m;
void init(string a, string b) {
    int n = a.size();
    v.resize(n);
    a1.resize(n + 1);
    a2 = c1 = c2 = t1 = t2 = m = a1;
    for (int i = 0; i < n; i++) {
        a1[i + 1] = a1[i] + (a[i] == 'A');
        a2[i + 1] = a2[i] + (b[i] == 'A');
        c1[i + 1] = c1[i] + (a[i] == 'C');
        c2[i + 1] = c2[i] + (b[i] == 'C');
        t1[i + 1] = t1[i] + (a[i] == 'T');
        t2[i + 1] = t2[i] + (b[i] == 'T');
        m[i + 1] = m[i] + (a[i] != b[i]);
    }
}
int get_distance(int x, int y) {
    x++, y++;
    int d1 = a2[y] - a2[x - 1], d2 = a1[y] - a1[x - 1];
    int d3 = c2[y] - c2[x - 1], d4 = c1[y] - c1[x - 1];
    int d5 = t2[y] - t2[x - 1], d6 = t1[y] - t1[x - 1];
    if (d1 != d2 || d3 != d4 || d5 != d6) {
        return -1;
    } else {
        return ((m[y] - m[x - 1] + 1) / 2);
    }
}

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