제출 #1288851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288851		harryleee	DNA 돌연변이 (IOI21_dna)	C++20	35 / 100	26 ms	4848 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
int dif[100000], A_T[100000], a_A[100000], b_A[100000], a_T[100000], b_T[100000];

bool check(int x, int y){
    int numA_a = a_A[y], numA_b = b_A[y], numT_a = a_T[y], numT_b = b_T[y];
    if (x > 0){
        numA_a -= a_A[x - 1];
        numA_b -= b_A[x - 1];
        numT_a -= a_T[x - 1];
        numT_b -= b_T[x - 1];
    }
    return ((numA_a == numA_b) && (numT_a == numT_b));
}

int get_distance(int x, int y){
    if (!check(x, y)) return -1;
    int res = dif[y] - A_T[y];
    if (x > 0) res -= (dif[x - 1] - A_T[x - 1]);
    return res;
}

void init(string a, string b){
    int n = a.size();
    for (int i = 0; i < n; ++i){
        if (a[i] != b[i] && a[i] != 'C') dif[i]++;
        if (i > 0) dif[i] += dif[i - 1];

        if (a[i] == 'A' && b[i] == 'T') A_T[i]++;
        if (i > 0) A_T[i] += A_T[i - 1];

        if (a[i] == 'A') a_A[i]++;
        if (i > 0) a_A[i] += a_A[i - 1];

        if (a[i] == 'T') a_T[i]++;
        if (i > 0) a_T[i] += a_T[i - 1];

        
        if (b[i] == 'A') b_A[i]++;
        if (i > 0) b_A[i] += b_A[i - 1];

        if (b[i] == 'T') b_T[i]++;
        if (i > 0) b_T[i] += b_T[i - 1];
    }
    return;
}

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