Submission #630656

#	Time	Username	Problem	Language	Result	Execution time	Memory
630656		tmncollins	Mutating DNA (IOI21_dna)	C++17	0 / 100	47 ms	10460 KiB

dna

#include "dna.h"
#include <stdio.h>
#include <vector>
#include <string>
#include <map>

// g++ grader.cpp dna.cpp -o dna

using namespace std;

vector<vector<int>> prefix;
map<char, int> base;

void init(string a, string b) {
    int size = a.size() + 1;
    prefix = vector<vector<int>> (size);
    base['A'] = 0;
    base['C'] = 1;
    base['G'] = 1;

    prefix[0] = {0, 0, 0, 0, 0, 0, 0}; // A, C, T (1), A, C, T (2), diff

    for (int k = 1; k < size; k++) {
        int i = k-1;
        prefix[k] = prefix[k-1];
        prefix[k][base[a[i]]]++;
        prefix[k][base[b[i]]+3]++;
        if (a[i] != b[i]) prefix[k][6]++;
    }

}

int get_distance(int x, int y) {
    vector<int> a = prefix[x], b = prefix[y+1];
    for (int k = 0; k < 7; k++) b[k] -= a[k];

    for (int k = 0; k < 3; k++) if (b[k] != b[k+3]) return -1;

    int ans = b[6] / 2;
    if (b[6] % 2) ans += 1;

    return ans;
}

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