Submission #1015724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015724		jairRS	Mutating DNA (IOI21_dna)	C++17	22 / 100	1541 ms	6840 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;

string a, b;
int n;

vector<int> prefix_a[3]; // 1 - based
vector<int> prefix_b[3]; // 1 - based
vector<int> prefix_dif;  // 1 - based

enum Nucleotide
{
    A,
    T,
    C
};

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

    for (int i = 0; i < 3; i++)
    {
        prefix_a[i] = vector<int>(n + 1, 0);
        prefix_b[i] = vector<int>(n + 1, 0);
        prefix_dif.resize(n + 1, 0);
    }

    string letters = "ATC";

    map<char, int> freq_a, freq_b;
    for (int i = 1; i <= n; i++)
    {
        freq_a[a[i - 1]]++;
        freq_b[b[i - 1]]++;

        prefix_dif[i] = (a[i - 1] != b[i - 1]) + prefix_dif[i - 1];

        for (int j = 0; j < 3; j++)
        {
            char letter = letters[j];

            prefix_a[j][i] = freq_a[letter];
            prefix_b[j][i] = freq_b[letter];
        }
    }
}

int count_letter(int letter, int i, int j, char str)
{
    // i, j are 0-based
    i++;
    j++;

    vector<int> prefix;
    if (str == 'a')
        prefix = prefix_a[letter];
    else
        prefix = prefix_b[letter];

    return prefix[j] - prefix[i - 1];
}

int get_distance(int x, int y)
{
    // substrings are only composed of 'A' and 'T'

    vector<int> letter_count_a(3), letter_count_b(3);
    for (int letter = 0; letter < 3; letter++)
    {
        letter_count_a[letter] = count_letter(letter, x, y, 'a');
        letter_count_b[letter] = count_letter(letter, x, y, 'b');

        if (letter_count_a[letter] != letter_count_b[letter])
            return -1;
    }

    // counts are good

    int dif = prefix_dif[y + 1] - prefix_dif[x]; // prefix_dif is 1 based
    return dif / 2;
}

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