Submission #1052848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052848		amongus_pvp	Mutating DNA (IOI21_dna)	C++17	0 / 100	21 ms	5080 KiB

dna

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int ALPHABET_SIZE = 3;

vector<vector<int>> prefixSumA;
vector<vector<int>> prefixSumB;

void init(string a, string b) {
    int n = a.size();
    
    // Initialize prefix sum arrays
    prefixSumA.assign(ALPHABET_SIZE, vector<int>(n + 1, 0));
    prefixSumB.assign(ALPHABET_SIZE, vector<int>(n + 1, 0));
    
    // Mapping from character to index: A -> 0, T -> 1, C -> 2
    auto charToIndex = [](char c) -> int {
        if (c == 'A') return 0;
        if (c == 'T') return 1;
        return 2;  // 'C'
    };
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < ALPHABET_SIZE; ++j) {
            prefixSumA[j][i + 1] = prefixSumA[j][i];
            prefixSumB[j][i + 1] = prefixSumB[j][i];
        }
        prefixSumA[charToIndex(a[i])][i + 1]++;
        prefixSumB[charToIndex(b[i])][i + 1]++;
    }
}

int get_distance(int x, int y) {
    vector<int> freqA(ALPHABET_SIZE), freqB(ALPHABET_SIZE);
    
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        freqA[i] = prefixSumA[i][y + 1] - prefixSumA[i][x];
        freqB[i] = prefixSumB[i][y + 1] - prefixSumB[i][x];
    }
    
    if (freqA != freqB) return -1;

    // Calculate the number of mutations required
    string subA = "", subB = "";
    for (int i = x; i <= y; ++i) {
        subA += freqA[0]-- > 0 ? 'A' : (freqA[1]-- > 0 ? 'T' : 'C');
        subB += freqB[0]-- > 0 ? 'A' : (freqB[1]-- > 0 ? 'T' : 'C');
    }
    
    int swaps = 0;
    for (size_t i = 0; i < subA.size(); ++i) {  // Use size_t instead of int
        if (subA[i] != subB[i]) {
            swaps++;
        }
    }
    
    return swaps / 2;
}

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