Submission #544055

#	Time	Username	Problem	Language	Result	Execution time	Memory
544055		Leo121	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	8552 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int lim = 1e5;
int pfa[2][lim + 2];
int pfc[2][lim + 2];
int pft[2][lim + 2];
int adif[2][lim + 2];
int cdif[2][lim + 2];
int tdif[2][lim + 2];
void init(std::string a, std::string b) {
    int longitud = a.size();
    for(int i = 0; i < longitud; ++ i){
        if(a[i] == 'A'){
            pfa[0][i + 1] ++;
            if(b[i] == 'C'){
                adif[0][i + 1] ++;
            }
            else if(b[i] == 'T'){
                adif[1][i + 1] ++;
            }
        }
        else if(a[i] == 'C'){
            pfc[0][i + 1] ++;
            if(b[i] == 'A'){
                cdif[0][i + 1] ++;
            }
            else if(b[i] == 'T'){
                cdif[1][i + 1] ++;
            }
        }
        else{
            pft[0][i + 1] ++;
            if(b[i] == 'A'){
                tdif[0][i + 1] ++;
            }
            else if(b[i] == 'C'){
                tdif[1][i + 1] ++;
            }
        }
        if(b[i] == 'A'){
            pfa[1][i + 1] ++;
        }
        else if(b[i] == 'C'){
            pfc[1][i + 1] ++;
        }
        else{
            pft[1][i + 1] ++;
        }
        for(int j = 0; j <= 1; ++ j){
            pfa[j][i + 1] += pfa[j][i];
            pfc[j][i + 1] += pfc[j][i];
            pft[j][i + 1] += pft[j][i];
            adif[j][i + 1] += adif[j][i];
            cdif[j][i + 1] += cdif[j][i];
            tdif[j][i + 1] += tdif[j][i];
        }
    }
}

int get_distance(int x, int y) {
    x ++;
    y ++;
    if((pfa[0][y] - pfa[0][x - 1] != pfa[1][y] - pfa[1][x - 1]) || (pfc[0][y] - pfc[0][x - 1] != pfc[1][y] - pfc[1][x - 1]) || (pft[0][y] - pft[0][x - 1] != pft[1][y] - pft[1][x - 1])){
        return -1;
    }
    int res = 0;
    res += min(adif[0][y] - adif[0][x - 1], cdif[0][y] - cdif[0][x - 1]);
    res += min(adif[1][y] - adif[1][x - 1], tdif[0][y] - tdif[0][x - 1]);
    res += min(cdif[1][y] - cdif[1][x - 1], tdif[1][y] - tdif[1][x - 1]);
    res += (max(adif[0][y] - adif[0][x - 1], cdif[0][y] - cdif[0][x - 1]) - min(adif[0][y] - adif[0][x - 1], cdif[0][y] - cdif[0][x - 1])) * 2;
	return res;
}

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