제출 #1288856

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

dna

#include<bits/stdc++.h>
#include "dna.h"

using namespace std;
const int maxn = 1e5;
int dif[maxn + 1], AinT[maxn + 1], aa[maxn + 1], at[maxn + 1], ba[maxn + 1], bt[maxn + 1];

int get_distance(int l, int r){
    l++; r++;
    if ((aa[r] - aa[l - 1]) != (ba[r] - ba[l - 1])) return -1;
    if ((bt[r] - bt[l - 1]) != (at[r] - at[l - 1])) return -1;
    int res = dif[r] - dif[l - 1]; 
    res += (AinT[r] - AinT[l - 1]);
    return res;
}

void init(string a, string b){
    a = " " + a;
    b = " " + b;
    for (int i = 1; i < a.size(); ++i){
        if (a[i] == 'A' && a[i] != b[i]) dif[i]++;
        if (a[i] == 'T' && b[i] == 'C') dif[i]++;
        dif[i] += dif[i - 1];
        AinT[i] = AinT[i - 1] + (a[i] == 'A' && b[i] == 'C');
        aa[i] = aa[i - 1] + (a[i] == 'A');
        at[i] = at[i - 1] + (a[i] == 'T');
        ba[i] = ba[i - 1] + (b[i] == 'A');
        bt[i] = bt[i - 1] + (b[i] == 'T');
    }
    return;
}

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