Submission #438099

#	Time	Username	Problem	Language	Result	Execution time	Memory
438099		Monchito	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	6460 KiB

dna

#include "dna.h"
#include <vector>
#include <algorithm>
using namespace std;
 
string A, B;
int n;
 
vector<int> pref1, pref2, pref3, pref4, pref5, pref6;
 
void init(std::string a, std::string b) {
    A = a, B = b;
    n = (int)A.size();
 
    pref1 = pref2 = pref3 = pref4 = pref5 = pref6 = vector<int>(n+1, 0);
    
    for(int i=0; i<n; i++) {
        if(A[i] == B[i]) {
            pref1[i+1] += pref1[i];
            pref2[i+1] += pref2[i];
            pref3[i+1] += pref3[i];
            pref4[i+1] += pref4[i];
            pref5[i+1] += pref5[i];
            pref6[i+1] += pref6[i];
            continue;
        }
 
        if(A[i] == 'A') {
            if(B[i] == 'T') pref1[i+1]++;
            else if(B[i] == 'C') pref2[i+1]++;
        }
 
        else if(A[i] == 'T') {
            if(B[i] == 'A') pref3[i+1]++;
            else if(B[i] == 'C') pref4[i+1]++;
        }
 
        else {
            if(B[i] == 'A') pref5[i+1]++;
            else if(B[i] == 'T') pref6[i+1]++;
        }
 
        pref1[i+1] += pref1[i];
        pref2[i+1] += pref2[i];
        pref3[i+1] += pref3[i];
        pref4[i+1] += pref4[i];
        pref5[i+1] += pref5[i];
        pref6[i+1] += pref6[i];
    }
}
 
int get_distance(int x, int y) {
    int msk=1, ret=0, aux=-1;
 
    int p1 = pref1[y+1] - pref1[x],
    p2 = pref2[y+1] - pref2[x],
    p3 = pref3[y+1] - pref3[x],
    p4 = pref4[y+1] - pref4[x],
    p5 = pref5[y+1] - pref5[x],
    p6 = pref6[y+1] - pref6[x];
 
    msk &= (p1 + p2 == p3 + p5);
    ret += p1 + p2;
    aux = min(p1, p3); p3 -= aux;
    aux = min(p2, p5); p5 -= aux;
    p4 += p3, p6 += p5;
    p1 = p2 = p3 = p5 = 0;
 
    msk &= (p3 + p4 == p1 + p6);
    ret += p3 + p4;
    aux = min(p1, p3); p1 -= aux;
    aux = min(p4, p6); p6 -= aux;
    p2 += p1, p5 += p6;
    p3 = p4 = p1 = p6 = 0;
 
    msk &= (p5 + p6 == p2 + p4);
    ret += p5 + p6;
    aux = min(p5, p2); p2 -= aux;
    aux = min(p6, p4); p4 -= aux;
    p1 += p2, p3 += p4;
    p5 = p6 = p2 = p4 = 0;
 
	return (msk)? ret : -1;
}

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