Submission #438088

#	Time	Username	Problem	Language	Result	Execution time	Memory
438088		Monchito	Mutating DNA (IOI21_dna)	C++17	21 / 100	50 ms	5156 KiB

dna

#include "dna.h"
#include <vector>
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;

    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) * 2;

    msk &= (p3 + p4 == p1 + p6);
    ret += (p3 + p4) * 2;

    msk &= (p5 + p6 == p2 + p4);
    ret += (p5 + p6) * 2;

	return (msk)? ret/3 : -1;
}

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