제출 #1189556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189556		pxsit	Mutating DNA (IOI21_dna)	C++20	100 / 100	20 ms	4876 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

int AT[100001], TA[100001], AC[100001], CA[100001], CT[100001], TC[100001];

void init(string a, string b) {
    for (int i=0;i<a.size();i++){
        AT[i] = (i == 0 ? 0 : AT[i-1]) + (a[i] == 'A' && b[i] == 'T');
        TA[i] = (i == 0 ? 0 : TA[i-1]) + (a[i] == 'T' && b[i] == 'A');
        AC[i] = (i == 0 ? 0 : AC[i-1]) + (a[i] == 'A' && b[i] == 'C');
        CA[i] = (i == 0 ? 0 : CA[i-1]) + (a[i] == 'C' && b[i] == 'A');
        TC[i] = (i == 0 ? 0 : TC[i-1]) + (a[i] == 'T' && b[i] == 'C');
        CT[i] = (i == 0 ? 0 : CT[i-1]) + (a[i] == 'C' && b[i] == 'T');
    }
}

int get_distance(int x, int y) {
    int at = AT[y], ta = TA[y], ac = AC[y], ca = CA[y], tc = TC[y], ct = CT[y];
    if(x != 0)
        at -= AT[x-1], ta -= TA[x-1], ac -= AC[x-1], ca -= CA[x-1], tc -= TC[x-1], ct -= CT[x-1];
    int ans = min(at, ta) + min(ac, ca) + min(tc, ct),m1 = min(at, ta), m2 = min(ac,ca), m3 = min(ct, tc);
    at -= m1, ta -= m1; 
    ac -= m2, ca -= m2; 
    tc -= m3, ct -= m3; 
    if(at-ta+ac-ca != 0 || ct-tc+ca-ac != 0 || ta-at+tc-ct != 0) return -1;
        return ans + ((ac+ca+at+ta+tc+ct)/3)*2;
}

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