Submission #836958

#	Time	Username	Problem	Language	Result	Execution time	Memory
836958		FulopMate	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	6248 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> ac, ca, at, ta, ct, tc;

void init(string a, string b) {
    n = a.length();
    ac.assign(n+1, 0);
    ca.assign(n+1, 0);
    at.assign(n+1, 0);
    ta.assign(n+1, 0);
    ct.assign(n+1, 0);
    tc.assign(n+1, 0);
    for(int i = 0; i < n; i++){
        if(a[i] == 'A' && b[i] == 'C')ac[i+1]++;
        if(a[i] == 'C' && b[i] == 'A')ca[i+1]++;
        if(a[i] == 'A' && b[i] == 'T')at[i+1]++;
        if(a[i] == 'T' && b[i] == 'A')ta[i+1]++;
        if(a[i] == 'C' && b[i] == 'T')ct[i+1]++;
        if(a[i] == 'T' && b[i] == 'C')tc[i+1]++;
        ac[i+1] += ac[i];
        ca[i+1] += ca[i];
        at[i+1] += at[i];
        ta[i+1] += ta[i];
        ct[i+1] += ct[i];
        tc[i+1] += tc[i];
    }
}

int get_distance(int x, int y) {
    int o_ac = ac[y+1]-ac[x];
    int o_ca = ca[y+1]-ca[x];
    int o_at = at[y+1]-at[x];
    int o_ta = ta[y+1]-ta[x];
    int o_ct = ct[y+1]-ct[x];
    int o_tc = tc[y+1]-tc[x];
    int ans = 0;
    int curr;

    curr = min(o_ac, o_ca);
    ans += curr;
    o_ac -= curr; o_ca -= curr;
    
    curr = min(o_at, o_ta);
    ans += curr;
    o_at -= curr; o_ta -= curr;
    
    curr = min(o_ct, o_tc);
    ans += curr;
    o_ct -= curr; o_tc -= curr;

    curr = min(o_ac, min(o_ct, o_ta));
    ans += curr*2;
    o_ac -= curr; o_ct -= curr; o_ta -= curr;

    curr = min(o_ca, min(o_tc, o_at));
    ans += curr*2;
    o_ca -= curr; o_tc -= curr; o_at -= curr;

    if(o_ac || o_ca || o_at || o_ta || o_ct || o_tc)return -1;
	return ans;
}

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