Submission #1106628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106628		kheira	Mutating DNA (IOI21_dna)	C++17	0 / 100	22 ms	5896 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#include "dna.h"
using namespace std;

vector<int> A_a, C_a, T_a;
vector<int> A_b, C_b, T_b;

void init(string a, string b) {
    int n = a.size();
    A_a = C_a = T_a = vector<int>(n + 1, 0);
    A_b = C_b = T_b = vector<int>(n + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        A_a[i] = A_a[i - 1] + (a[i - 1] == 'A');
        C_a[i] = C_a[i - 1] + (a[i - 1] == 'C');
        T_a[i] = T_a[i - 1] + (a[i - 1] == 'T');
        
        A_b[i] = A_b[i - 1] + (b[i - 1] == 'A');
        C_b[i] = C_b[i - 1] + (b[i - 1] == 'C');
        T_b[i] = T_b[i - 1] + (b[i - 1] == 'T');
    }
}

int get_distance(int x, int y) {
    int a_count_A = A_a[y + 1] - A_a[x];
    int a_count_C = C_a[y + 1] - C_a[x];
    int a_count_T = T_a[y + 1] - T_a[x];
    
    int b_count_A = A_b[y + 1] - A_b[x];
    int b_count_C = C_b[y + 1] - C_b[x];
    int b_count_T = T_b[y + 1] - T_b[x];
    if (a_count_A != b_count_A || a_count_C != b_count_C || a_count_T != b_count_T) {
        return -1;  
    }
    int makanch_AC = abs(a_count_A - b_count_A); 
    int makanch_AT = abs(a_count_A - b_count_T); 
    int makanch_CT = abs(a_count_C - b_count_T); 
    int direct_swaps = makanch_AC / 2 + makanch_AT / 2 + makanch_CT / 2;
    int two_step_swaps = (makanch_AC % 2) + (makanch_AT % 2) + (makanch_CT % 2);
    
    return direct_swaps + 2 * two_step_swaps;
}

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